Sharp higher-difference families

Proof of Theorem 6.1

Return to the Euler variables of address zero and put \(X=P+Q\), \(\tau=i\mathcal E\mathcal F\), \(\epsilon=1+\tau\). Direct rearrangement of (5.6) gives

The divided powers of \(G\) are integral by the same component formulas used above. Thus modulo \(2\mathcal A_0\), \(\gamma_k(H_0)\) equals the divided power of \(\gamma_2(X)+\epsilon X\). The identity

has an odd integer scalar. Every term involving \(\epsilon^j\) for \(j\geq2\) vanishes modulo two. The surviving zero and first powers give

The multiplication coefficient in the second term is \(2k-1\), also odd. By the odd moments (5.4) and independence,

The \(\tau\)-weighted moment vanishes because it contains an odd power of each Euler variable. Therefore the first term of (6.3) evaluates to one modulo two and the second to zero. Hence \(\mathcal L(\gamma_k(H_0))\) is odd at every order, including order zero. This proves

In the base-row expansion (5.9), every \(s>0\) term has at least one extra bit after division by \(2^k k!\). Thus the same exact valuation holds at every starting row. The extra-bit transfer (5.19) proves it for address one as well.

It remains to track possible ties in the mixed-step expansion. For local orders \(m_\nu\geq1\) and total \(M\), the excess over \(L\) is at least

The first bracket is nonnegative, and equality requires every \(m_\nu\) to be one or two. Two or more occurrences of two make the second bracket positive, since the intervening factorial interval then contains an even number. Exactly one occurrence of two can tie only when \(k\) is even; its binomial coefficient can have the minimally allowed valuation only if its associated step is even.

The all-one multi-index contributes one after normalization by \(2^L\). When \(k\) is even, each even step supplies exactly one further tied term, again with normalized residue one. For example, \(\binom H2=H(H-1)/2\) attains \(v_2(H)-1\) exactly when \(H\) is even; all remaining factors and the exact normalized order-\(k+1\) difference are odd. Thus the total normalized parity is one for odd \(k\), and \(1+e\) for even \(k\). This proves the classification. In the homogeneous case, \(e\) is zero or \(k\), so it is even whenever \(k\) is even, proving (6.1).

Back to statement · Read statement and proof side by side · Permalink · Source line 784 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 6.3

For \(k=2^r\geq4\), put \(q=k/2\), which is even. Normalize the exact expansion (5.31) by \(2^q\) before reducing modulo two. Its \(u\)th auxiliary term has excess \(u+\lfloor(k-u)/2\rfloor-q=\lfloor u/2\rfloor\). Only auxiliary indices zero and one can therefore survive:

Here \(V\equiv\tau\pmod2\) and \(\tau^2\equiv1\pmod2\). Since \(q\) is even and \(\epsilon\tau\equiv\epsilon\pmod2\), this reduces to \(\gamma_k(X)+\epsilon G\gamma_{k-1}(X)\). Moreover, \(G\equiv\gamma_2(X)+\tau Q\pmod2\). After evaluation, every term with a single \(\tau\) vanishes, so the second contribution reduces to

The \(\gamma_2(X)\) product has scalar \(\binom{k+1}{2}\), which is even because \(4\mid k\). The other contribution expands as

An odd summand would require \(k-a\) to be odd and \(\mu_{k-a}\) to be odd. By Lemma 5.2, this requires \(k-a=1\). Then \(a=k-1\) is not a power of two and \(\mu_a\) is even. Hence the second contribution is zero modulo two.

For the first contribution, independence gives \(\mathcal L(\gamma_k(P+Q))=\sum_{a=0}^k\mu_a\mu_{k-a}\). The parity generating series of these convolution moments is

Its coefficient is one at every \(k=2^r\geq4\). Thus the normalized moment in (6.6) is odd and

Inserting \(U^{4n}=(1+4H_2)^n\) introduces only corrections with strictly higher valuation, by the filtered bound at orders \(k+s\) for \(s>0\). The equality consequently holds at every starting row.

For mixed steps the all-one local multi-index gives the claimed leading term. A higher term of total order \(M>k\) has excess at least

Hence the leading term cannot cancel.

At order one, \(a_1\) in (5.28) has valuation four and the Newton tail starts at valuation six; its shifted value remains exact. In the step expansion a local order two can lose at most one bit through its binomial coefficient, so every correction is still above \(4+v_2(H_1)\). At order two, \(a_2\) has valuation six and the next coefficient has lower bound eight from the stronger filtration. A total-order-three correction loses at most one bit, so it stays above the leading valuation six, while later orders gain still more. The same argument proves exactness for both mixed steps.

Back to statement · Read statement and proof side by side · Permalink · Source line 881 · Claim record · Lean coverage · Code · Worked examples