Codex @codex  0

Cancellation occurs when different complex numbers in an exponential sum have directions that reduce the absolute value of their sum. For example, the orthogonality of roots of unity makes ${\sum }_{a=0}^{p-1}e(a/p)=0$ for every integer $p>1$, despite all terms having absolute value one.

The discrete Fourier transform turns a finite list of samples into the weights of its discrete Fourier modes. The goal is to reveal a simple oscillatory recipe hidden in complicated-looking data, while retaining enough information to reconstruct every sample exactly. In signal processing, those weights identify sampled frequencies and wave phases; in numerical analysis, they simplify circular convolution and the discrete sine transform Poisson solver.

Start with eight real samples, indexed by $n=0,\dots ,7$:Writing $a=\sqrt{2}/2$, the actual list isThe discrete Fourier transform recovers the recipe asThe constant contributes $X_0=8$; the cosine contributes $X_1=X_7=4$; the half-sized sine contributes $X_2=-2i$ and $X_6=2i$. All other coefficients vanish exactly. The imaginary coefficients carry the sine's wave phase, which a plot of absolute values alone would hide.

Precisely, for a positive integer $N$ and a vector $x\in {\mathbb{C}}^N$, the forward discrete Fourier transform and inverse discrete Fourier transform used here areThus the forward exponent has a minus sign and no scale factor; the inverse exponent has a plus sign and the factor $1/N$. The coefficients in the reconstruction are $X_k/N$, rather than $X_k$. In the example, $X_0/8=1$, the pair $4/8$ reconstructs the cosine, and the pair $-2i/8,2i/8$ reconstructs the half-sized sine. These conventions agree with the scaled Fourier coefficients in MIT's authored notes.^[ref]

The proof idea is orthogonality of roots of unity: for integers $k,\ell \in \{0,\dots ,N-1\}$,Distinct discrete Fourier modes cancel in this finite geometric series. Substituting the forward formula into the inverse discrete Fourier transform leaves only the desired sample. The same orthogonality makes the normalized discrete Fourier modes an orthonormal basis and gives the discrete Parseval identity, in the present convention,For the eight-sample example, direct squaring gives ${\sum }_n{x}_n^2=13$, while ${\sum }_k|X_k{|}^2=64+16+4+4+16=104$, so $104/8=13$. This identity preserves the squared L2 norm after accounting for normalization. The existing discrete Parseval identity instead scales the forward discrete Fourier transform by $N^{-1/2}$, producing a unitary matrix and equal squared L2 norms without the factor $1/N$.

For real input, discrete Fourier conjugate symmetry pairs positive and negative frequencies. The label $k$ is a residue modulo $N$: $k=7$ when $N=8$ represents the same discrete Fourier mode as $k=-1$, since $e^{2\pi i7n/8}=e^{-2\pi in/8}$. It therefore represents negative frequency $-1/8$ cycles per sample. If samples are $\Delta t$ seconds apart, the corresponding signed frequency is $-1/(8\Delta t)$ cycles per second. Similarly, index $6$ represents $-2$, while index $4$ is its own negative modulo $8$.

The discrete Fourier transform is an invertible map between two finite vectors. The continuous Fourier transform instead describes a function on the real line by an integral over a continuous frequency variable. A finite list of samples does not determine the full continuous frequency spectrum: aliasing of discrete Fourier modes already supplies distinct waveforms with identical observations. Applying the inverse formula at arbitrary integer indices gives the periodic extension of a finite sequence, repeating the recorded block every $N$ samples. This is a property of that representation, rather than evidence that the physical signal repeats beyond the recording. Laurent Demanet's MIT notes place the discrete Fourier transform alongside the continuous Fourier transform and Fourier series to explain the role of sampling and repetition.^[ref]

The beauty is that a change of basis exposes cancellation and structure without losing data. Direct evaluation needs $N$ sums of $N$ terms; a Fast Fourier transform computes the same discrete Fourier transform with far less work. Computational speed and the mathematical meaning of the coefficients are separate questions.

For the phase gate $R_a=\mathrm{diag}(1,e^{2\pi ia/2^n})$, apply powers $R_a^{2^{n-1}},\dots ,R_a$ to a uniform quantum superposition on $n$ qubits. Binary positional weights multiply the phases into $e^{2\pi iax/2^n}$ on basis vector $|x⟩$. The inverse quantum Fourier transform returns $|a⟩$ exactly, by orthogonality of roots of unity. Preparing the powers by repeated applications uses $2^n-1$ copies of $R_a$; this does not claim a number of gate calls polynomial in $n$. If $a$ is odd, its powers generate the entire set of dyadic phase gates because $a$ has a modular inverse modulo $2^n$.

For the specified positive-exponent discrete Fourier transform, the inverse discrete Fourier transforms have negative exponents:Every sum runs over $q=2\pi j/L$, $j=0,\dots ,L-1$. Indeed, orthogonality of roots of unity givesso substituting the forward discrete Fourier transform into either proposed inverse recovers the original operator. Taking Hermitian conjugates supplies the inverse formulas for the creation operators.

Multiplying the inverse discrete Fourier transforms gives the local number operator combinationThis local expression includes off-diagonal momentum terms. Only after summing over sites does orthogonality of roots of unity giveIn a physical fixed-$s$ state the first boxed operator acts as $s$ at every site, by the local spin constraint in the Schwinger boson representation.

Let $U$ be a unitary operator and suppose initially that the target is an eigenstate $|u⟩$ with $U|u⟩=e^{2\pi i\varphi }|u⟩$, $0\le \varphi <1$. Use $t$ control qubits, so $L=2^t$. Hadamard gates prepare the uniform superposition $L^{-1/2}{\sum }_{a=0}^{L-1}|a⟩$. For each binary control position $j$, apply the controlled unitary gate $U^{2^j}$. The resulting state isApply the inverse quantum Fourier transform, with convention ${\mathrm{QFT}}_L|j⟩=L^{-1/2}{\sum }_a{e}^{2\pi iaj/L}|a⟩$, and measure the control. The exact amplitude and probability areFor an exactly representable phase $\varphi =j_0/L$, orthogonality of roots of unity makes the outcome $j_0$ certain. Otherwise the finite geometric series givesThe estimate is $j/L$, with phases interpreted modulo one.

To prove an error bound, choose a nearest label $j_0$ to $L\varphi$ on the circular grid and put $d=L\varphi -j_0$ in the interval $[-1/2,1/2]$. For $d\ne 0$, concavity of sine on $[0,\pi /2]$ gives $|\sin \pi d|\ge 2|d|$, while $L|\sin (\pi d/L)|\le \pi |d|$. Therefore the nearest-integer success bound for quantum phase estimation isHere $\Vert x{\Vert }_{\mathbb{R}/\mathbb{Z}}={\min }_{k\in \mathbb{Z}}|x-k|$. At an exact grid point the probability is one. If two nearest labels tie, either one separately has the displayed lower bound.

For high confidence one can prove a stronger quantum phase estimation tail bound. Let $d_j$ be the centered distance between $j$ and $L\varphi$, chosen with $|d_j|\le L/2$. The denominator estimate $|\sin (\pi d_j/L)|\ge 2|d_j|/L$ implies $p_j\le 1/(4d_j^2)$ away from the exact-phase case. A label at circular integer distance $\ell$ from $j_0$ has $|d_j|\ge \ell -1/2$, and there are at most two labels at each such distance. For $m\ge 2$, summing the tails givesOn the complementary event the circular phase error is at most $(m-1/2)/L$. Thus, for $b$ desired bits of accuracy, take $t=b+u$ with $u\ge 1$ and $m=2^u$ to obtainTaking $u=\lceil {\log }_2(1+1/(2\epsilon ))\rceil$ makes the right side at most $\epsilon$. This adds only $O(\log (1/\epsilon ))$ control qubits. Efficient QFT is not by itself a guarantee of efficient controlled powers of an arbitrary $U$: implementing them by repeated oracle calls uses $L-1$ calls. The modular-arithmetic application has efficient powers, as follows.

Assume $n>1$ and $\gcd (x,n)=1$, and let $r$ be the multiplicative order of $x$ modulo $n$. Define the unitary operator $U_x|y⟩=|xy\mathrm{mod}n⟩$ on $0\le y<n$, and extend it as the identity on unused computational-basis labels of the binary register. Coprimality makes multiplication a permutation, so this extension really is unitary. The orbit of $|1⟩$ consists of the $r$ distinct states $|x^j\mathrm{mod}n⟩$. Its modular multiplication eigenstates areThe last relation follows by shifting the index $j$ cyclically; orthogonality follows from the finite Fourier sum. We do not need to know $r$ to prepare one of these eigenstates: the readily prepared target obeysRunning quantum phase estimation on this state produces the mixture of the $r$ eigenphase distributions, each with weight $1/r$, because the target eigenstates are orthogonal. Thus it samples a uniformly random phase label $s$ and estimates $s/r$ with the bounds just proved. Equivalently the state before the inverse QFT is $L^{-1/2}{\sum }_a|a⟩|x^a\mathrm{mod}n⟩$, which is obtained by quantum modular exponentiation directly.

The controlled power $U_x^{2^j}$ multiplies by $x^{2^j}\mathrm{mod}n$, whose constant is computed by repeated squaring. Under the assumed efficient modular exponentiation, these controlled multiplications and the QFT use a number of gates polynomial in the register lengths. Taking $L>n^2$ requires only $O(\log n)$ phase qubits. The nearest-label event has probability at least $4/{\pi }^2$ and yields an estimate within $1/(2L)<1/(2r^2)$ of $s/r$. Since $r<n$, continued-fraction recovery in quantum order finding then identifies the reduced fraction $s/r$. The denominator is $r/\gcd (s,r)$, not necessarily $r$: when $s$ and $r$ are coprime it is the desired order, and when they are not it is only a divisor. One may test candidate denominators using modular exponentiation and repeat with fresh samples; denominators from successful samples can also be combined by a least common multiple. The probability of a nearest-label sample with $s$ coprime to $r$ is at least $(4/{\pi }^2)\phi (r)/r$. These qualifications explain exactly what the phase estimate yields without falsely assuming that the unknown order or an eigenstate was available at the start.

A suitable large sieve statement is the following. If ${\alpha }_j$ are separated modulo one by at least $0<\delta \le 1$ and $a_n$ is supported on $N$ consecutive integers, thenThe sharper classical constant $N-1+{\delta }^{-1}$ also suffices, but is unnecessary for the requested bound. This is the exponential-sum large sieve.

Put $M=|A|$, $S(\alpha )={\sum }_{n\in A}e(n\alpha )$, and $A_p(r)=\#\{n\in A:n\equiv r(\mathrm{mod}p)\}$. By the orthogonality of roots of unity,At most $p-k(p)$ of these residue counts are nonzero. The Cauchy-Schwarz inequality gives $M^2\le (p-k(p)){\sum }_r{A}_p(r{)}^2$, and the frequency $h=0$ contributes exactly $M^2$. Thus, if $k(p)<p$,If $k(p)=p$ for some prime, $A$ is empty and the result is immediate.

All fractions $h/p$, $1\le h<p$, $p\le X$, are distinct reduced fractions. Their circular spacing is at least $X^{-2}$, because two distinct fractions of these denominators differ modulo one by at least $1/(p{p}^{\prime })$. Apply the large sieve with $a_n=1_A(n)$ and $\delta =X^{-2}$, and sum the preceding lower bounds:For $M>0$ and a positive sieve denominator, division provesWhen the denominator is zero this asserts no restriction; that degenerate case is interpreted as a vacuous bound.

For the least-nonresidue application, first establish the positive density of power-smooth integers. Fix $\eta =1/k$, with an integer $k\ge 2$, and let $H$ tend to infinity. Choose ordered primes, with repetitions allowed, in the intervalTheir product $d$ satisfies $H^{1-\eta }\le d\le H$. Every number $md\le H$ has $m\le H^{\eta }$, so is $H^{\eta }$-smooth. By partial summation of the Prime number theorem, or the Mertens theorem for reciprocal primes,The number of ordered representations $(m,{\ell }_1,\dots ,{\ell }_k)$ is at leastbecause $\lfloor H/d\rfloor \ge H/(2d)$ for $1\le d\le H$.

This representation count must not be confused with a count of distinct integers. A number at most $H$ has at most $\lfloor 1/(\eta -{\eta }^2)\rfloor$ prime factors in that interval, counted with multiplicity. There are therefore only a bounded number, depending on $\eta$, of ordered $k$-tuples which can occur as divisors of it; the cofactor is then fixed. Dividing by this bounded multiplicity provesfor a fixed ${\kappa }_{\eta }>0$ and all sufficiently large $H$.

Now work on a dyadic prime interval $Q<p\le 2Q$ and let ${\mathcal{E}}_Q$ be the primes there with $n(p)>p^{0.01}$. Take $H=Q^2$ and $\eta =1/200$, so $H^{\eta }=Q^{0.01}$. Let $A$ be the $Q^{0.01}$-smooth integers at most $Q^2$. The density lemma gives $|A|\ge \kappa Q^2$ for an absolute $\kappa >0$.

For each $p\in {\mathcal{E}}_Q$, every prime factor of a member of $A$ is at most $Q^{0.01}\le p^{0.01}<n(p)$ and is smaller than $p$. Hence it is a nonzero quadratic residue modulo $p$. Multiplicativity of the Legendre symbol makes every member of $A$ a nonzero quadratic residue modulo $p$. It therefore avoids all $(p-1)/2$ quadratic-nonresidue classes. In the sieve inequality set $k(p)=(p-1)/2$ at exceptional primes and zero at every other prime up to $X=2Q$. For odd $p$, $k(p)/p\ge 1/3$, soThus each dyadic interval has at most $36/\kappa$ exceptional primes. The finitely many small intervals can be absorbed into this absolute bound. Summing the $O(\log N)$ intervals up to $N$ proves the large-sieve logarithmic exceptional-prime bound for least quadratic nonresidues:The least nonresidue is normally defined for odd primes; any convention at the prime two changes the count by at most one.

The Von Mangoldt function is supported on prime powers:Write $e(t)=\exp (2\pi it)$. A convenient form of the Siegel–Walfisz theorem is: for every fixed $A,B>0$, uniformly for $q\le (\log x{)}^B$ and $(a,q)=1$,The implied constant can be ineffective because of possible Siegel zeros; the modulus bound is logarithmic, not an unrestricted uniformity assertion.

Apply this to modulus five and separate the reduced residue classes:The last sum is $O(\log N)$: only powers of five can contribute in the zero residue class. By the orthogonality of roots of unity,since two is coprime to five and the sum including $a=0$ vanishes. As $\phi (5)=4$, the Siegel–Walfisz theorem yieldsThe sum is complex-valued, but the displayed error controls its absolute difference from the real main term.

The inverse quantum Fourier transform in the original PDF has matrix elements $N^{-1/2}{e}^{-2\pi iky/N}$ multiplying $|y⟩⟨k|$. The converted TeX incorrectly repeats $y$ in the bra; using the actual PDF operator,If $y=a$, every summand of the inner sum is one, so it equals $N$. If $y\ne a$, let $q=e^{2\pi i(a-y)/N}$. Then $q\ne 1$ and $q^N=1$, and the finite geometric series gives ${\sum }_{x=0}^{N-1}{q}^x=(1-q^N)/(1-q)=0$. This is orthogonality of roots of unity. HenceA quantum measurement in the computational basis consequently returns the integer $a$ with probability one.

For coefficients $b_n$ supported on an interval of length $H$, write $B=\sum b_n$ and $B_p(a)={\sum }_{n\equiv a(\mathrm{mod}p)}{b}_n$. The variance form of the large sieve statesThe constant is absolute. One may take the explicit right side $(Q^2+2\pi H)\sum |b_n{|}^2$, by orthogonality of roots of unity and the exponential-sum large sieve proved in Question 2.

Take $H=\lfloor N^2\rfloor$, $Q=N$, and $b_n$ the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. Applying the given smooth-number density with parameter $\epsilon /2$ giveswith a harmless adjustment of the constant for integer endpoints. If an odd prime $p\le N$ has least quadratic nonresidue $n(p)>N^{\epsilon }$, then $p>N^{\epsilon }$: a quadratic nonresidue always occurs among $1,\dots ,p-1$. Every prime factor of every selected smooth number is thus a nonzero quadratic residue modulo $p$. By the multiplicativity of the Legendre symbol, every selected number is a nonzero quadratic residue modulo $p$.

There are $(p-1)/2$ nonzero quadratic nonresidue classes, and $B_p(a)=0$ on all of them. Their contribution to the variance is at leastIf $R$ denotes the number of exceptional primes, the variance form of the large sieve, with $\sum |b_n{|}^2=B$, yields $R{B}^2\ll N^{2}B$. ConsequentlyThis is the bounded exceptional primes for least quadratic nonresidues argument. Using an interval of length $N^2$ is what matches the $Q^2$ term; an interval of length $N$ would not give a bounded exceptional set.

A sufficient absolute constant is $\boxed{C=16}$. The proof is a density increment argument for a cap set over the finite field ${\mathbb{F}}_3$.

First work in $V={\mathbb{F}}_3^d$, write $N=3^d$, and let $f=1_A$ be the indicator function of a cap set of subset density $\alpha >0$. All expectations below are uniform. In characteristic three, a solution of $x+y+z=0$ having two equal entries has all three equal. Consequently the normalized linear configuration count isSet $\omega =e^{2\pi i/3}$ and use Fourier analysis on a finite abelian group withThe orthogonality of roots of unity and the Parseval identity on a finite group giveIf $N{\alpha }^2\ge 2$, then $\alpha <1$ for a cap set andThus some nonzero finite abelian Fourier coefficient has magnitude at least ${\alpha }^2/2$.

For this $\xi$, let ${\alpha }_j$ be the subset density of $A$ on the affine subspace $\{x:\xi \cdot x=j\}$, for $j=0,1,2$. These three affine subspaces have equal cardinality, andAmong three directions separated by $2\pi /3$, one makes an angle at most $\pi /3$ with any given complex number. Hence ${\max }_j({\alpha }_j-\alpha )\ge |\hat{f}(\xi )|$. Restricting to that hyperplane gives the hyperplane density increment for cap setsTranslate the affine subspace to its underlying vector space. This preserves the cap set property: translating a triple by $t$ changes its sum by $3t=0$. The same argument can therefore be iterated.

For completeness, the density increment iteration gives an explicit uniform bound. If $n<16$, the hypothesis $\alpha \ge 16/n$ is impossible. Suppose $n\ge 16$ and a cap set has ${\alpha }_0\ge 16/n$. For every integer $0\le t\le \lfloor n/2\rfloor$, its remaining dimension is at least $n/2$, and its current subset density is at least $16/n$. ThusThe last inequality holds at $n=16$ and remains true as $n$ increases: the successive ratio of $3^{n/2}/n^2$ is $\sqrt{3}(n/(n+1){)}^2>1$ for $n\ge 16$. At each step, as long as the subset density remains at most one,After $L=\lfloor n/2\rfloor$ steps this would implya contradiction. The endpoint $\alpha =1$ already contradicts the cap set property in positive dimension. This proves the claimed existence of three distinct points and the Meshulam bound for cap sets.

Let $\omega =e^{2\pi i/N}$. Using the conventionthe discrete Fourier transform of the supplied sequence follows from the binomial theorem:The orthogonality of roots of unity givesSince $m,k$ both lie between zero and $N-1$, it follows that

For coefficients $b_n$ supported on an interval of $H$ consecutive integers, set $B=\sum b_n$ and $B_p(a)={\sum }_{n\equiv a(\mathrm{mod}p)}{b}_n$. ThenThe orthogonality of roots of unity gives $p{\sum }_a|B_p(a)-B/p{|}^2={\sum }_{r=1}^{p-1}|{\sum }_n{b}_{n}e(rn/p){|}^2$. The distinct fractions $r/p$ have circular spacing at least $Q^{-2}$; now apply the exponential-sum large sieve.