LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-07

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Fourier analysis of margulis adjacency

Statement

Let $T_{1} (x, y) = (x + 2 y, y)$ , $T_{2} (x, y) = (x, y + 2 x)$ modulo $m$ . Define the forward operator $K f (x) = f (T_{1} x) + f (T_{1} x + e_{1}) + f (T_{2} x) + f (T_{2} x + e_{2})$ . For real mean-zero $f$ , put $g = ∣ \hat{f} ∣$ and $Q (g) = \sum_{z} 2 g (z) [g (T_{2}^{- 1} z) ∣ \cos (π z_{1} / m) ∣ + g (T_{1}^{- 1} z) ∣ \cos (π z_{2} / m) ∣] .$ Then $g (0) = 0$ , $∥ f ∥^{2} = \sum_{z} g (z)^{2}$ , $∣ ⟨ f, K f ⟩ ∣ \leq Q (g)$ , and the full Margulis adjacency $A$ satisfies $∣ ⟨ f, A f ⟩ ∣ \leq 2 Q (g)$ .

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

For the normalized negative-exponent Fourier transform on $(Z / m Z)^{2}$ , the characters are an orthonormal basis, and $f = \sum_{b} \hat{f} (b) χ_{b}, ∥ f ∥^{2} = \sum_{b} ∣ \hat{f} (b) ∣^{2}, \sum_{x} f (x) = 0 ⟺ \hat{f} (0) = 0.$ For every invertible matrix $T$ over $Z / m Z$ , and $g (x) = f (T x + a)$ , $\hat{g} (y) = ω^{y \cdot T^{- 1} a} \hat{f} (T^{- T} y) .$ (Finite torus fourier orthogonality and affine change).

[F2]

The Margulis graph on $(Z / m Z)^{2}$ is symmetric and $8$ -regular, with $m^{2}$ vertices, for every $m \geq 1$ . One specified neighbor is computable in polynomial time in $\log (m + 2)$ ; the whole adjacency list is computable in $O (m^{2} poly (\log (m + 2)))$ bit operations. (Margulis family is constant degree and neighbor computable).

[F3]

For integer $m \geq 1$ , the Margulis–Gabber–Galil graph has at $(x, y)$ the four slots $(x + 2 y, y)$ , $(x + 2 y + 1, y)$ , $(x, y + 2 x)$ , $(x, y + 2 x + 1)$ and the four inverse slots $(x - 2 y, y)$ , $(x - 2 y - 1, y)$ , $(x, y - 2 x)$ , $(x, y - 2 x - 1)$ , with multiplicities and fixed points retained. (Margulis gabber galil graph).

Proof

1.1

The Fourier identities give $g (0) = 0$ and the stated norm equality. Since $T_{1}^{T} = T_{2}$ , the transform of the first pair of summands in $K f$ is $(1 + ω^{z_{1}}) \hat{f} (T_{2}^{- 1} z)$ ; the second pair gives $(1 + ω^{z_{2}}) \hat{f} (T_{1}^{- 1} z)$ . The phase uses $T_{j}^{- 1} e_{j} = e_{j}$ .

2.1

Parseval's inner-product identity (obtained by expanding both functions in the orthonormal character basis) expresses $⟨ f, K f ⟩$ as the coefficient inner product. Apply the triangle inequality and $∣ 1 + e^{2 i θ} ∣ = 2 ∣ \cos θ ∣$ to obtain $Q (g)$ . The absolute cosines are independent of residue representatives.

step 1.1algebra

3.1

The four slots defining $K$ are exactly the forward slots in the Margulis construction, and the other four are their inverses. Inverse permutations are the adjoints of the forward permutation operators under uniform counting, so $A = K + K^{*}$ . Therefore $⟨ f, A f ⟩ = 2 Re ⟨ f, K f ⟩$ , proving the last bound. For the singleton torus every mean-zero function vanishes and all displayed sums are zero.

F3F2step 2.1∎

Depends on

Used by

Margulis diamond weight bound Lemma

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §8.2 Theorems8.7–8.8, pp71–72; only the reduction, not the sharp constant. (standard reference, not scraped)