Lemma UNIQUE: A set of linear equations (no term multiplied by 0) will not have a unique solution if it contains more unknowns than equations.

Proof: The set of values for N unknowns can be viewed as an N- dimensional space. The solutions to a single linear equation form an N-1-dimensional hyperplane in this space. The solution to M such independent equations is the intersection of M such independent hyperplanes, forming an N-M dimensional space. Spaces greater than 0-dimensional contain multiple points, representing multiple solutions to the set of M equations with N unknowns. When the set of equations is not independent, there are effectively even fewer than M of them.

Theorem 4N/3: Given a number S, all the values of the sequence r, and N equations of type 1, 2, and/or 3 below, there will be at least 4N/3 unknowns.

  a_i = a_{i-1} + m_{i-S/2}    /* 1 */
  r_i = m_{i-S} + y_i          /* 2 */
  m_i = r_i + a_i + x_i        /* 3 */

Proof:Suppose a set of equations has I 1's, J 2's, and K 3's. We can put a lower bound on the number of unknowns that will appear.

1 alone:  3I - (I-1) = 2I+1, all but one a_i can be an a_{i-1}.
2 alone:  2J, since all r's are known.
3 alone:  3K, since all r's are known.
1+2: 2I+2J-min(I,J)+1, since m_{i-S} and m_{i-S/2} can overlap.
1+3: 2I+3K-2min(I,K)+1, since m's and a's can overlap.
2+3: 2J+3K-min(J,K) since m's can overlap (r's are known).
1+2+3: 2I+2J+3K-min(I,J)-2min(I,K)-min(J,K)+min(I,J,K)+1,
  since the overlap of m's is only 2x not 3x

What is 2I+2J+3K-min(I,J)-2min(I,K)-min(J,K)+min(I,J,K)+1?

I<J<K: 2I+2J+3K-I-2I-J+I+1 = J+3K+1   > (4/3)(I+J+K)
I<K<J: 2I+2J+3K-I-2I-K+I+1 = 2J+2K+1  > (4/3)(I+J+K)
J<I<K: 2I+2J+3K-J-2I-J+J+1 = J+3K+1   > (4/3)(I+J+K)
J<K<I: 2I+2J+3K-J-2K-J+J+1 = 2I+J+K+1 > (4/3)(I+J+K)
K<I<J: 2I+2J+3K-I-2K-K+K+1 = I+2J+K+1 > (4/3)(I+J+K)
K<J<I: 2I+2J+3K-J-2K-K+K+1 = 2I+J+K+1 > (4/3)(I+J+K)

Therefore N equations will have at least 4N/3 unknowns.

Corollary N/3: Theorem 4N/3, combined with lemma UNIQUE), imply that that given N equations of the form 1, 2, or 3, at least N/3 additional equations explaining a, m, y, and x must be given before the unknowns in the original equations have a unique solution.

Gotta show that, not only can you not solve for all 4N/3 unknowns without finding N/3 more equations, you can't find the values for any M unknowns without finding at least M/3 more equations.

Note that this treats the sequences m, x, and y as truly independent. In the generator ISAAC, it is known that values of x and y are chosen from the previous SIZE values of m in some deterministic fashion. Guessing the choice correctly for some value of x or y would supply an additional equation with no extra unknowns. There are 2^8 possible guesses for each value. If the choices are independent for each value, it is not practical today to guess more than about 5 values this way.

ISAAC starts with 256 unknowns (the initial values in m[]). Combine that with theorem 4/3, and after the user sees N results, there are 256+(N/3) more unknowns that linear equations. In order for Gaussian Elimination to be useful, extra equations must be found faster than extra unknowns are produced.