Effective Numberings, Reductions, Resources, and Randomness: Examples

After j loop iterations, the accumulator is $a+j$ and the counter is $y-j$, for $0\le j\le y$: initially this is the parsed input, and one increment/decrement preserves the formula. The counter reaches zero after exactly y iterations, giving output $a+y$. At y=0 the loop is skipped. These are the addition recursion and its finite numeral routines in F2, so the compiled index e has the advertised total binary function.

Specialization F1 writes the stored numeral $\mathrm{bin}(3)=11$ before the input numeral and sends the two-entry tuple to e. For y=0 the arity header is 110, the block for 11 is 11011 and the block for 0 is 100, so the exact grouped encoding is $11011011100$. For y=4 it is $110110111110100$, since the block for 100 is $1110100$. The first calculation leaves accumulator 3 unchanged and outputs 11; the second has accumulator values $3,4,5,6,7$ and counter values $4,3,2,1,0$, outputting 111. Thus canonical input numerals 0 and 100 produce 11 and 111 respectively, and F1 gives the asserted equality for every y.

The integer 5 is prime: it is greater than one, and its possible positive proper divisors 2,3,4 do not divide it (remainders 1,2,1 respectively). Therefore F2 constructs the field used here, with residues 0,1,2,3,4. Its nonzero inverses are $1^{-1}=1$, $2^{-1}=3$, $3^{-1}=2$, $4^{-1}=4$, as $1,6,6,16$ all have remainder one. In particular division by the difference $3-1=2$ is valid.

Solving $a+b=2$ and $3a+b=4$ gives $2a=2$, hence $a=3\cdot 2=1$ and $b=1$. Direct substitution gives $h(1)=2$, $h(3)=4$. More generally outputs u,v give $a=3(v-u)$, $b=u-a$, a unique seed as in F1. Each joint output has probability $1\mathrm{/}25$ and each marginal $1\mathrm{/}5$, so these two values are independent uniform. This counts all slopes, including zero when u=v.

For every seed, $h(0)=b$, $h(1)=a+b$, and $h(2)=2a+b=2h(1)-h(0)$. Thus $h(0)=0$ and $h(1)=0$ force b=a=0 and consequently $h(2)=0$. The event $(h(0),h(1),h(2))=(0,0,1)$ has probability zero, whereas three independent uniform values would give $1\mathrm{/}125$. This is a concrete failure of three-wise independence, consistent with the pairwise conclusion.

Five has no positive proper divisors other than one: 2,3,4 leave remainders 1,2,1. Thus F2 supplies ${\mathbb{F}}_5$, with distinct residues 0 through 4. At X=0, $XY-1=-1=4\mathrm{\ne }0$. At each nonzero X, the unique Y solving $XY=1$ is its inverse: $1\cdot 1=1$, $2\cdot 3=6=1$, $3\cdot 2=6=1$, $4\cdot 4=16=1$ modulo 5. Cancellation rules out any additional Y for the same X. These are all five possibilities for X, so exactly the four listed pairs are roots.

Each pair has mass $1\mathrm{/}25$, so the count gives probability $4\mathrm{/}25$. The formal coefficient of XY is one and its total degree is two; the constant term is nonzero but has degree zero, so it does not change total degree. F1 with m=2, d=2 and A equal to the field gives $\min (1,2\mathrm{/}5)=2\mathrm{/}5=10\mathrm{/}25$. Consequently $4\mathrm{/}25<10\mathrm{/}25$. The comparison is an upper bound, not a claimed equality; independence is used to give every pair the same mass.