MathLabs
TheoremProved

The extraction (orthogonality) identity

Statement

For every finite A⊂Z≥0A\subset\mathbb Z_{\ge0}, integer k≥1k\ge1 and n≥0n\ge0, rk(n)=∫01FA(α)k e(−nα) dαr_k(n) = \int_0^1 F_A(\alpha)^k\, e(-n\alpha)\, d\alpha, where rk(n)r_k(n) is the number of ordered kk-tuples from AA summing to nn.

Why is it true?

This is what lets us replace a purely combinatorial counting problem by a question about the size of an analytic integral: if we can show the integral is positive, a representation must exist.

Proof sketch

First note the orthogonality relation ∫01e(mα) dα\int_0^1 e(m\alpha)\, d\alpha=1=1 if m=0m=0, and =0=0 if m≠0m\neq 0: writing e(mα)=cos⁡(2πmα)+isin⁡(2πmα)e(m\alpha)=\cos(2\pi m\alpha)+i\sin(2\pi m\alpha), for m≠0m\neq0 this is a full number of periods of a sine/cosine wave over [0,1)[0,1), which integrates to 00; for m=0m=0 the integrand is the constant 11.

Now expand the kk-th power of the generating function: FA(α)k=(∑a∈Ae(aα))k=∑(a1,…,ak)∈Ake((a1+⋯+ak)α)F_A(\alpha)^k=\Big(\sum_{a\in A}e(a\alpha)\Big)^k=\sum_{(a_1,\dots,a_k)\in A^k} e\big((a_1+\cdots+a_k)\alpha\big), a finite sum over all ordered kk-tuples from AA, grouped by the exponent m=a1+⋯+akm=a_1+\cdots+a_k.

Multiply both sides by e(−nα)e(-n\alpha) and integrate term by term over [0,1)[0,1) (legitimate because the sum is finite, so integration and summation commute): ∫01FA(α)ke(−nα) dα=∑(a1,…,ak)∈Ak∫01e((a1+⋯+ak−n)α) dα\int_0^1 F_A(\alpha)^k e(-n\alpha)\,d\alpha=\sum_{(a_1,\dots,a_k)\in A^k}\int_0^1 e\big((a_1+\cdots+a_k-n)\alpha\big)\,d\alpha.

By the orthogonality relation, each summand on the right is 11 exactly when a1+⋯+ak=na_1+\cdots+a_k=n and 00 otherwise. So the whole sum collapses to exactly the count of tuples with a1+⋯+ak=na_1+\cdots+a_k=n, i.e. rk(n)r_k(n). This proves the identity exactly, with no approximation involved: it is an identity, not an asymptotic.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. G. H. Hardy, S. Ramanujan (1918). Asymptotic formulae in combinatory analysis · DOI:10.1112/plms/s2-17.1.75
  2. J. Bourgain, C. Demeter, L. Guth (2016). Proof of the main conjecture in Vinogradov's Mean Value Theorem for degrees higher than three · DOI:10.4007/annals.2016.184.2.7 · arXiv:1512.01565
  3. B. Green, T. Tao (2008). The primes contain arbitrarily long arithmetic progressions · DOI:10.4007/annals.2008.167.481 · arXiv:math/0404188