Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

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