# Reading roadmap: Manuscript

A cyclotomic-integer lemma controls polynomial values at roots of unity modulo p. Dividing a Fourier minor by its Vandermonde factors and evaluating derivatives proves that every square minor is nonzero. Invertibility then gives the support-sum bound and its converse, followed by sparse-polynomial and sumset consequences.

Source SHA-256: `f74c8847aeadab250fa55b4ff6830bcfa2c34e9f3f19fde9ef44f14ac3edcad2`. Indexed 21,450 characters.

Edges point from prerequisite to consumer. Solid proof edges are attributed inferences, not formal certificates; references remain candidates.

## Internal claim index

### Theorem 1 — `uncertainty`

Source lines 169–177.

Let $p$ be a prime number. If $f: \Z/p\Z \to \C$ is a non-zero function, then\footnote{This inequality was also discovered independently by Andr\'as Bir\'o \cite{frenkel} and Roy Meshulam (Vsevolod Lev, private communication). Given the number of times Lemma \ref{minors} appears to have been rediscovered in the literature it is in fact quite likely that this theorem has existed previously in some unpublished form.} $$ |\supp(f)| + |\supp(\hat f)| \geq p+1.$$ Conversely, if $A$ and $B$ are two non-empty subsets of $\Z/p\Z$ such that $|A| + |B| \

*Extractive statement; proof gist not independently reconstructed.*

Proof opening: Suppose for contradiction that we had a non-zero function $f$ such that $|\supp(f)| + |\supp(\hat f)| \leq p$. Then if we write $A := \supp(f)$, then we can find a set $\tilde A$ in $\Z/p\Z$ which is disjoint from $\supp(\hat f)$ and has cardinality equal to $|A|$. But this contradicts Corollary \ref{n-injective} since $Tf = 0$ but $f \neq 0$. Now we prove the converse. It will suffice to prove the claim when $|A| + |B| = p+1$, since the claim for $|A| + |B| > p+1$ then follows by applying the claim to subsets $A'$, $B'$ of $A$, $B$ respectively for which $|A'| + |B'| = p+1$, and then taking generic linear combinations as $A'$, $B'$ vary. We can then choose an $\tilde A$ in $\Z/p\Z$ of cardi


Candidate references: `minors` (internal_reference); `n-injective` (candidate_proof_dependency); `external:frenkel` (external_reference).

### Lemma 2 — `galois`

Source lines 190–195.

Let $p$ be a prime, $n$ be a positive integer, and let $P(z_1, \ldots, z_n)$ be a polynomial with integer co-efficients. Suppose that we have $n$ $p^{th}$ roots of unity $\omega_1, \ldots, \omega_n$ (not necessarily distinct) such that $P(\omega_1, \ldots, \omega_n) = 0$. Then $P(1, \ldots, 1)$ is a multiple of $p$.

*Extractive statement; proof gist not independently reconstructed.*

Proof opening: Write $\omega := e^{2\pi i/p}$, then for every $1 \leq j \leq n$ we have $\omega_j = \omega^{k_j}$ for some integers $0 \leq k_j < p$. If we then define the single-variable polynomial $Q(z)$ by $$ Q(z) := P(z^{k_1}, \ldots, z^{k_n}) \mod z^p-1,$$ where $R(z) \mod z^p - 1$ is the remainder when dividing $R(z)$ by $z^p - 1$ (or equivalently, taking the polynomial $R(z)$ and replacing $z^{qp+r}$ with $z^r$ for all $q \geq 1$ and $0 \leq r < p$), then we have $Q(\omega) = 0$ and $Q(1) = P(1, \ldots, 1)$. But $Q(z)$ is a polynomial of degree at most $p-1$ with integer coefficients, and thus must be an integer multiple of the minimal polynomial $1 + z + \ldots + z^{p-1}$ of $\omega$. The claim fol

### Lemma 3 — `minors`

Source lines 210–214.

Let $p$ be a prime and $1 \leq n \leq p$. Let $x_1, \ldots, x_n$ be distinct elements of $\Z/p\Z$, and let $\xi_1, \ldots, \xi_n$ also be distinct elements of $\Z/p\Z$. Then the matrix $( e^{2\pi i x_j \xi_k/p} )_{1 \leq j,k \leq n}$ has non-zero determinant.

*Extractive statement; proof gist not independently reconstructed.*

### Corollary 4 — `n-injective`

Source lines 271–276.

If $p$ is a prime, and $A, \tilde A$ are non-empty subsets of $\Z/p\Z$ such that $|A|=|\tilde A|$, then the linear transformation $T: l^2(A) \to l^2(\tilde A)$ defined by $Tf = \hat f|_{\tilde A}$ (i.e. we restrict the Fourier transform of $f$ to $\tilde A$) is invertible. Here we use $l^2(A)$ to denote those functions $f: G \to \C$ which are equal to zero outside of $A$.

*Extractive statement; proof gist not independently reconstructed.*

## External inputs and references

### [1] alon — `external:alon`

Source lines 344–347.

N. Alon, M. Nathanson, I. Ruzsa, The polynomial method and restricted sums of congruence classes, J. Number Theory 56 (1996), 404--417.


Candidate references: `section:1` (external_reference).

### [2] bkt — `external:bkt`

Source lines 347–351.

J. Bourgain, N. Katz, T. Tao, A sum-product estimate in finite fields, and applications, to appear, GAFA. {\tt math.CO/0301343}


Candidate references: `section:1` (external_reference).

### [3] k — `external:k`

Source lines 351–355.

J. Bourgain, S. Konyagin, Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order, C. R. Acad. Sci. Paris, Ser. I 337 (2003), 75--80.


Candidate references: `section:1` (external_reference).

### [4] candes — `external:candes`

Source lines 355–358.

E. Candes, J. Romberg, T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, preprint.


Candidate references: `section:1` (external_reference).

### [5] cauchy — `external:cauchy`

Source lines 358–361.

A.L. Cauchy, Recherches sur les nombres, J. \'Ecole Polytech. 9 (1813), 99-116.


Candidate references: `section:1` (external_reference).

### [6] davenport — `external:davenport`

Source lines 361–364.

H. Davenport, On the addition of residue classes, J. London Math. Soc. 10 (1935), 30--32.


Candidate references: `section:1` (external_reference).

### [7] d — `external:d`

Source lines 364–369.

J. Dieudonn\'e, Une propri\'et\'e des racines de l'unit\'e, Collection of articles dedicated to Alberto Gonz\'alez Dom\'inguez on his sixty-fifth birthday. Rev. Un. Mat. Argentina 25 (1970/71), 1--3.


Candidate references: `section:1` (external_reference).

### [8] donoho — `external:donoho`

Source lines 369–372.

D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM J. Appl. Math. 49 (1989), 906--931.


Candidate references: `section:1` (external_reference).

### [9] ei — `external:ei`

Source lines 372–376.

R.J. Evans, I.M. Stark, Generalized Vandermonde determinants and roots of unity of prime order, Proc. Amer. Math. Soc. 58 (1977), 51--54.


Candidate references: `section:1` (external_reference).

### [10] frenkel — `external:frenkel`

Source lines 376–379.

P. Frenkel, Simple proof of Chebotarev's theorem on roots of unity, preprint. {\tt math.AC/0312398}


Candidate references: `uncertainty` (external_reference); `section:1` (external_reference).

### [11] ggi — `external:ggi`

Source lines 379–382.

D. Goldstein, R. Guralnick, I. Isaacs, Inequalities for finite group permutation modules, preprint. {\tt math.GR/0310169}


Candidate references: `section:1` (external_reference).

### [12] mesh — `external:mesh`

Source lines 382–385.

R. Meshulam, An uncertainty inequality for finite abelian groups, preprint. {\tt math.CO/0312407}

### [13] newman — `external:newman`

Source lines 385–388.

M. Newman, On a theorem of Cebotarev, Linear and Multilinear Algebra 3 (1975/76), no. 4, 259--262.


Candidate references: `section:1` (external_reference).

### [14] prez — `external:prez`

Source lines 388–391.

T. Przebinda, Three uncertainty principles for a locally compact abelian group, preprint.


Candidate references: `section:1` (external_reference).

### [15] res — `external:res`

Source lines 391–395.

Yu. G. Re\v setnyak, Yu., New proof of a theorem of N. G. Cebotarev (Russian), Uspehi Mat. Nauk (N.S.) 10 (1955), no. 3(65), 155--157.


Candidate references: `section:1` (external_reference).

### [16] smith — `external:smith`

Source lines 395–398.

K.T. Smith, The uncertainty principle on groups, SIAM J. APpl. Math. 50 (1990), 876--882.


Candidate references: `section:1` (external_reference).

### [17] sl — `external:sl`

Source lines 398–402.

P. Stevenhagen, H.W. Lenstra Jr., Chebotar\"ev and his density theorem, Math. Intelligencer 18 (1996), no. 2, 26--37.


Candidate references: `section:1` (external_reference).

### [18] terras — `external:terras`

Source lines 402–407.

A. Terras, Fourier analysis on finite groups and applications. London Mathematical Society Student Texts, 43. Cambridge University Press, Cambridge, 1999.


Candidate references: `section:1` (external_reference).

## Coverage and limits

{"mode": "native_latex_index", "claims": 4, "sections": 1, "external_references": 18, "source_bibliography_entries": 18, "unresolved_bibliography": 0, "unresolved": 0}

- Reference edges are not certified proof dependencies. Edge direction is prerequisite → consumer.
- Numbers reflect simple source counters; labels and line anchors are authoritative.
- Extractive statements and proof openings are marked; they are not reconstructed proof gists.
- Macros, included files and custom counters require an expanded source or annotated fallback.