Two-dimensional pseudo-Paley cliques
Abstract
The two-dimensional cliques containing one in quartic pseudo-Paley graphs are exactly the odd-generator planes.
Definition 1.1 (Cyclotomic class character).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.chi (✓ std3).
Source. Repository-derived.
Commentary.
The power character labels the p+1 cyclotomic classes of the quartic finite field.
Definition 1.2 (Norm of an affine representative).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.Q (✓ std3).
Source. Repository-derived.
Commentary.
Q is the p-squared norm power of b+t; it is used on prime-field affine parameters.
Lemma 1.3 (Character through the norm).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.chi_eq_Q_pow (✓ std3). ∎
Source. Repository-derived.
Commentary.
The character factors as the norm power followed by the p-minus-one power.
Lemma 1.4 (A fixed prime-field element).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.pow_char_eq_self_of_pow_sub_one_eq_one (✓ std3). ∎
Source. Repository-derived.
Commentary.
A p-minus-one root of unity is fixed by the p-th power.
Lemma 1.5 (Quartic exponent factorization).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.q_factor (✓ std3). ∎
Source. Repository-derived.
Commentary.
All arithmetic is in the natural numbers; subtraction is truncated subtraction.
Lemma 1.6 (Parity of the norm).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.c_square_iff_even (✓ std3). ∎
Source. Repository-derived.
Commentary.
The norm of the indicated generator power lies in the prime field and is a square exactly when its exponent index is even.
Lemma 1.7 (Trace and norm prevent collapse).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.trace_norm_fixed_implies_fixed (✓ std3). ∎
Source. Repository-derived.
Commentary.
If both the relative trace and norm are fixed by the p-th power, their common source element is fixed as well.
Definition 1.8 (The affine norm polynomial).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.normPoly (✓ std3).
Source. Repository-derived.
Commentary.
The polynomial expression retains its leading coefficient one.
Lemma 1.9 (Two affine points share a class).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.cross_eq_iff (✓ std3). ∎
Source. Repository-derived.
Commentary.
When the trace coefficient is outside the prime field and the norm is inside it, proportional norms occur exactly for equal points or for a pair whose product is the norm.
Lemma 1.10 (The affine mate of infinity).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.infinity_cross_iff (✓ std3). ∎
Source. Repository-derived.
Commentary.
The prime-field norm direction has exactly the affine parameter zero.
Definition 1.11 (The projective pairing).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.projectiveMate (✓ std3).
Source. Repository-derived.
Commentary.
Option.none represents infinity. It exchanges infinity with zero and sends each nonzero parameter to C/t, avoiding total division at zero.
Lemma 1.12 (Nonsquares have no singleton orbits).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.projectiveMate_no_fixed_iff (✓ std3). ∎
Source. Repository-derived.
Commentary.
For a nonzero norm the projective pairing is fixed-point-free precisely when the norm is not a square.
Definition 1.13 (Projective class map).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.projectiveClass (✓ std3).
Source. Repository-derived.
Commentary.
Infinity represents one and an affine prime-field parameter represents b+t.
Lemma 1.14 (Nonzero affine norms).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.norm_Q_ne_zero (✓ std3). ∎
Source. Repository-derived.
Commentary.
An element outside the prime field cannot be cancelled by a prime-field affine parameter.
Lemma 1.15 (Quadratic expansion of the norm).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.Q_as_quadratic (✓ std3). ∎
Source. Repository-derived.
Commentary.
The norm has quadratic, trace and constant terms, with every affine parameter mapped into the quartic field.
Lemma 1.16 (Equality gives proportional norm directions).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.equal_projective_class_cross (✓ std3). ∎
Source. Repository-derived.
Commentary.
Equal class characters force the p-th-power cross product equality of the two nonzero norms.
Lemma 1.17 (Embedded prime-field parameters).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.prime_field_fixed (✓ std3). ∎
Source. Repository-derived.
Commentary.
Every embedded prime-field parameter is fixed by the p-th power.
Theorem 1.18 (At most two projective points per class).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.projective_fiber_card_le_two (✓ std3). ∎
Source. Repository-derived.
Commentary.
For b outside the prime field, the affine fiber equation is a nonzero polynomial of degree at most two. The infinity fiber has a nonzero linear equation on its affine part. The two bounds give at most two points in every projective fiber.
Definition 1.19 (Cyclotomic class).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.cyclotomicClass (✓ std3).
Citation. Shamil Asgarli; Chi Hoi Yip (2024). The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes. DOI: 10.48550/arXiv.2110.07176. URL: https://arxiv.org/abs/2110.07176v5.
Commentary.
Cyclotomic classes (p. 1): “Let . Let be the subgroup of with index , and let , …, be all the cosets of , where . The sets , , …, are called the -th cyclotomic classes of .”
The source takes the p+1-th cyclotomic classes of the quartic finite field. The primitive element is g, and natural exponents enumerate the cyclic subgroup generated by its p+1-th power.
Definition 1.20 (Connection set).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.connection (✓ std3).
Citation. Shamil Asgarli; Chi Hoi Yip (2024). The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes. DOI: 10.48550/arXiv.2110.07176. URL: https://arxiv.org/abs/2110.07176v5.
Commentary.
Definition 1.1 (pp. 1–2): “Suppose is a prime power, a positive integer such that , and ={, …, } ⊂ {0, 1, …, } with . Let , , …, be the -th cyclotomic classes of . The graph is defined to be the Cayley graph where D=⋃ⱼ₌₁ᵈ .”
Here the source parameters are q=p^4 and 2d=p+1; the selected natural indices form I. The union is the literal connection set.
Definition 1.21 (Pseudo-Paley graph).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.PP (✓ std3).
Citation. Shamil Asgarli; Chi Hoi Yip (2024). The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes. DOI: 10.48550/arXiv.2110.07176. URL: https://arxiv.org/abs/2110.07176v5.
Commentary.
Definition 1.1 (pp. 1–2): “Suppose is a prime power, a positive integer such that , and ={, …, } ⊂ {0, 1, …, } with . Let , , …, be the -th cyclotomic classes of . The graph is defined to be the Cayley graph where D=⋃ⱼ₌₁ᵈ .”
SimpleGraph.fromRel supplies the symmetric irreflexive relation of the additive Cayley graph; the difference is y-x.
Definition 1.22 (Asgarli–Yip Conjecture 5.9).
Formalization. D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.claim (✓ std3).
Citation. Shamil Asgarli; Chi Hoi Yip (2024). The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes. DOI: 10.48550/arXiv.2110.07176. URL: https://arxiv.org/abs/2110.07176v5.
Commentary.
Conjecture 5.9 (p. 17): “Let be a -dimensional subspace in , such that . Then is a clique in for some if and only if ⊕ , where and is an odd integer.”
The prime p is odd, g has order p^4-1, and V is a two-dimensional ZMod p-subspace containing one. The source’s ‘for some I’ means I is contained in Finset.range (p+1) and has cardinality Nat.div (p+1) 2. The direct sum is Submodule.span of one and the indicated generator power. Natural odd indices enumerate the same powers as odd integer indices, because the order p^4-1 is even.
Theorem 1.23 (Classification of the two-dimensional cliques).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.result (✓ std3). ∎
Resolves. Problems/asgarli-yip-2021-pseudo-paley-two-dimensional-cliques (proved) by D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.result.
Source. Repository-derived.
Acknowledgement. Shamil Asgarli; Chi Hoi Yip (2024). The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes. DOI: 10.48550/arXiv.2110.07176. URL: https://arxiv.org/abs/2110.07176v5.
Commentary.
The p+1 projective points map to cyclotomic classes with at most two points per fiber. A clique fits into (p+1)/2 classes, forcing every fiber to be a pair. The mate of infinity selects a generator power in the zeroth class. Its norm is a square exactly for even indices; a square norm gives a singleton fiber, so clique indices are odd. Conversely, an odd index gives a nonsquare norm and the fixed-point-free pairing exchanges zero with infinity and pairs the other parameters by C/t. Its classes form the required index set.
References
- Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.PP - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.Q - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.Q_as_quadratic - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.c_square_iff_even - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.chi - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.chi_eq_Q_pow - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.claim - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.connection - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.cross_eq_iff - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.cyclotomicClass - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.equal_projective_class_cross - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.infinity_cross_iff - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.normPoly - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.norm_Q_ne_zero - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.pow_char_eq_self_of_pow_sub_one_eq_one - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.prime_field_fixed - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.projectiveClass - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.projectiveMate - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.projectiveMate_no_fixed_iff - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.projective_fiber_card_le_two - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.q_factor - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.result - Truth anchor:
D5/S3/Combinatorics/PseudoPaley/TwoDimensionalCliques.trace_norm_fixed_implies_fixed