Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Spectral properties of generalized Paley graphs and their associated irreducible cyclic codes

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Generalized Paley graph spectra and cyclic code weights are the same datum: each eigenvalue is an affine function of a codeword weight.

desk verdict A useful dictionary between GP-graph spectra and code weights, with a real but peripheral flaw in the complement formula for disconnected graphs. read the letter →

arxiv 1908.08097 v3 pith:XFKTF7JG submitted 2019-08-21 math.CO cs.ITmath.IT

Ricardo A. Podestá , Denis E. Videla This is my paper · ORCID
classification math.COcs.ITmath.IT MSC 94B1505C2505C5011P05
keywords generalizedPaleygraphsirreduciblecycliccodesGaussianperiodsstronglyregularRamanujantwo-weightCayleygraphspectrafinitefields
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper builds a bridge between two objects that live on the same finite field: the generalized Paley graph $\Gamma(k,q)$, whose vertices are field elements and whose edges connect elements differing by a nonzero $k$-th power, and the irreducible $p$-ary cyclic code $\mathcal{C}(k,q)$ of length $n=(q-1)/k$. The central result is an affine identity: when $k$ divides $(q-1)/(p-1)$, the eigenvalue $\lambda_\gamma$ of the graph indexed by $\gamma$ equals $n - \frac{p}{p-1} w(c_\gamma)$, where $w(c_\gamma)$ is the Hamming weight of the codeword labelled by $\gamma$. When the graph is connected, the multiplicities also match, so the full spectrum of either object determines the other. The authors use this to give explicit integral spectra in the semiprimitive case, for all $\Gamma(3,q)$ and $\Gamma(4,q)$ under natural divisibility assumptions, and for the eleven exceptional two-weight code pairs.

What carries the argument

The load-bearing object is the Gaussian period $\eta_i^{(k,q)} = \sum_{x\in C_i} \zeta_p^{\mathrm{Tr}_{q/p}(x)}$, a character sum over one coset of the subgroup of $k$-th powers in $\mathbb{F}_q^*$. For a Cayley graph over an abelian group, each eigenvalue is a character sum over the connection set; here that sum reindexes to a Gaussian period, giving $\mathrm{Spec}(\Gamma(k,q))$ directly from the periods. The matching formula $w(c_\gamma)=\frac{p-1}{pk}(q-1-k\eta_i)$ expresses every codeword weight as an affine function of the same period. Comparing the two expressions yields the identity in Theorem 5.1 and transfers every known code-spectrum computation into a graph-spectrum computation.

What would settle it

Take $(k,q)=(3,25)$, so $p=5$ and $k$ divides $(q-1)/(p-1)=6$; enumerate $\mathbb{F}_{25}$, build the connection set $R_3$, form the $25\times 25$ adjacency matrix of $\Gamma(3,25)$, and list all 25 codewords $\mathrm{Tr}_{25/5}(\gamma\omega^{3i})$ for $i=0,\ldots,7$. If the 25 eigenvalues are not $\{[8]^1,[3]^8,[-2]^{16}\}$ or if $\lambda_\gamma = 8 - \frac{5}{4} w(c_\gamma)$ fails for a single $\gamma$, the central relation is false; the same brute-force check can be run on any small pair satisfying $k \mid (q-1)/(p-1)$.

Watch

Extended reading notes

Core claim

For $q=p^m$ and $k$ dividing $q-1$, the paper considers $\Gamma(k,q)=\mathrm{Cay}(\mathbb{F}_q,R_k)$ with $R_k=\{x^k: x\neq 0\}$, and the code $\mathcal{C}(k,q)$ whose codewords are the trace vectors $c_\gamma=(\mathrm{Tr}_{q/p}(\gamma\omega^{ki}))_{i=0}^{n-1}$. The central claim, Theorem 5.1, is that if $k$ also divides $(q-1)/(p-1)$, then every eigenvalue $\lambda_\gamma$ of the graph, computed through additive characters of $\mathbb{F}_q$, and the weight $w(c_\gamma)$ of the corresponding codeword satisfy $\lambda_\gamma = n - \frac{p}{p-1}w(c_\gamma)$, with $n=(q-1)/k$. For a connected graph the multiplicity of each eigenvalue is exactly the number of codewords of the corresponding weight, so the spectrum of the graph and the weight distribution of the code determine each other completely. The paper applies this dictionary to produce explicit spectra of semiprimitive generalized Paley graphs, of $\Gamma(3,q)$ and $\Gamma(4,q)$ when the divisibility condition holds, and of the graphs attached to the eleven exceptional pairs; in these cases the graphs turn out to be integral and, in the two-weight cases, strongly regular.

Load-bearing premise

The explicit spectra all rest on imported Gaussian-period evaluations and exceptional weight formulas that the paper does not re-derive; if those formulas carry hidden hypotheses or errors, the corresponding spectra in Theorems 3.3, 6.1, 6.3, and 7.1 inherit the failure.

Editorial extensions

If this is right

  • Known weight distributions of irreducible cyclic codes automatically give spectra of generalized Paley graphs, and conversely, whenever $k$ divides $(q-1)/(p-1)$; the two computations become interchangeable.
  • Semiprimitive pairs $(k,q)$ give connected integral strongly regular graphs with three explicit eigenvalues, and their complements are also strongly regular; for $s$ odd they are Latin square graphs, providing complete sets of mutually orthogonal Latin squares of order $p^{m/2}$.
  • The only semiprimitive generalized Paley graphs that are Ramanujan are the classical Paley graphs plus the $k=3,4,5$ families listed in Theorem 4.1, and every semiprimitive complement is Ramanujan.
  • If the graph attached to a code is Ramanujan and the code's minimum distance $d$ satisfies $d \le (p-1)n/p$, then $d \ge \frac{p-1}{p}(n - 2\sqrt{n-1})$; this converts an expansion property of the graph into a distance guarantee of the code.
  • The eleven exceptional two-weight irreducible cyclic codes yield connected strongly regular graphs whose spectra and parameters are explicitly computed for the first eight pairs; the remaining three pairs are stated to be too large for readable tables.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: because the identity runs in both directions, any newly discovered two-weight irreducible cyclic code satisfying the divisibility condition would immediately produce a strongly regular graph, so the graph side gives an independent test of the conjecture that the exceptional list (7.1) is complete.
  • Editorial inference: the Ramanujan-to-distance inequality in Corollary 5.4 can be read as a coding-theoretic reflection of the optimal spectral-expansion bound for regular graphs; optimizing the same relation may yield minimum-distance bounds even for non-Ramanujan graphs in the family.
  • Editorial inference: replacing the absolute trace by another linear functional, or dropping the divisibility assumption, would replace the exact identity by a comparison between a twisted Cayley graph and a shortened or punctured code; this is a testable way to measure how much of the dictionary survives.
  • Editorial inference: the same Gaussian-period machinery gives spectra for the complementary graph and for the coset graphs in the disjoint-union decomposition of the complement, so the relation plausibly extends to those components as well.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies generalized Paley graphs Γ(k,q)=Cay(F_q,R_k), where R_k is the subgroup of k-th powers in F_q^*, and the associated irreducible p-ary cyclic codes C(k,q) of length n=(q-1)/k. The main claim is a spectral dictionary: under the extra divisibility condition k | (q-1)/(p-1), the graph eigenvalue λ_γ and the Hamming weight w(c_γ) of the corresponding codeword satisfy λ_γ = n - (p/(p-1))w(c_γ), so that the spectrum of the graph and the weight distribution of the code determine each other. Building on this relation, the authors express the spectra of Γ(k,q) and its complement in terms of Gaussian periods, give explicit spectra and strongly-regular parameters for semiprimitive pairs, characterize which semiprimitive GP-graphs are Ramanujan, compute Spec(Γ(3,q)) and Spec(Γ(4,q)) from known cyclic-code weight distributions, and tabulate spectra for the first eight exceptional Schmidt-White pairs. Theorems 4.1, 6.1, and 6.3 are supported by explicit arithmetic checks, and the central relation (5.1) is derived directly from character sums and the cited weight formula rather than from the paper's own conclusions.

Significance. If the central relation (5.1) stands, it is a clean and useful bridge between two well-studied objects: every known weight distribution of an irreducible cyclic code gives the spectrum of a generalized Paley graph, and conversely. The paper makes this transfer explicit in several nontrivial families, including all semiprimitive graphs, the k=3 and k=4 families, and the exceptional two-weight codes. The Ramanujan characterization in Theorem 4.1 and the primitive-divisor checks in Theorems 6.1 and 6.3 are concrete and verifiable, and the paper is honest about its reliance on the external Gaussian-period formulas of Ding-Yang and the weight formulas of Schmidt-White. The dictionary relation itself is not circular and appears sound. The main weakness is a false statement about complement spectra in Theorem 2.1 for disconnected graphs; this does not affect the central dictionary relation, which is used only in connected cases, but it must be corrected.

major comments (2)
  1. [Theorem 2.1, Eq. (2.2)] The formula for Spec(Γ̅(k,q)) is false when μ>0. If Γ is disconnected with eigenvalue n of multiplicity 1+μn, then the all-ones vector gives the complement eigenvalue (k−1)n with multiplicity 1, while the μn principal eigenvectors orthogonal to the all-ones vector give eigenvalue −1−n, not (k−1)n. A concrete counterexample is q=16, k=5: here Γ(5,16)≅4K_4, with n=3 and μ=1, and the stated complement spectrum {[12]^4,[0]^{12}} is not the spectrum of the actual complement K_{4,4,4,4}, which is {[12]^1,[0]^3,[−4]^{12}}. The correct statement should replace the principal part of the complement spectrum with {[(k−1)n]^1, [−1−n]^{μ n}} and keep [−1−η_{i_j}]^{μ_{i_j} n} for the periods η_{i_j}≠n. Since all later uses of complement spectra occur in the connected case μ=0, the main dictionary and the subsequent theorems survive, but Theorem 2.1 as stated is incorrect.
  2. [Section 7, Theorem 7.1] The theorem announces the spectra for all eleven exceptional pairs, but the proof and Tables 3–6 actually provide data only for the first eight; the pairs (163,41^81), (323,3^144), and (499,5^249) are explicitly omitted as 'quite unmanageable'. Either the statement should be restricted to the eight pairs for which spectra are given, or the missing spectra should be supplied, so that the theorem's claim matches the evidence presented.
minor comments (4)
  1. [Section 5, proof of Theorem 5.1] The proof refers to 'Proposition 2.1' when citing the spectrum of Γ(k,q); this is Theorem 2.1.
  2. [Equations (3.4)–(3.5)] The typesetting of expressions such as '−√q+1/k' is ambiguous; it should be printed as (−√q+1)/k to prevent misreading as −√q + 1/k.
  3. [Section 1 and throughout] There are several typographical errors, including 'whit', 'integerdivide', and 'Propisition'; these should be corrected in a final pass.
  4. [Remark 6.5(ii)] The remark correctly notes that for k=3t and k=4t with t>1, the method of Section 5 does not directly apply; this limitation should also be reflected in the introductory summary to avoid overstating the scope of the k=3 and k=4 computations.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 5.1 is a legitimate translation of external Gaussian-period identities into a graph-code dictionary.

full rationale

The paper's central bridge, Theorem 5.1, is derived from two ingredients that are not the theorem itself: the character-sum expression for Cayley eigenvalues (equations (2.3)-(2.6) in Theorem 2.1) and Ding-Yang's external weight formula, quoted verbatim as (5.2) from [12]. Substituting lambda_gamma = eta_i^{(k,q)} into w(c_gamma) = ((p-1)/(pk))(q-1-k*eta_i^{(k,q)}) gives (5.1) by algebra; no parameter is fitted and no conclusion is presupposed. The subsequent spectra (Theorems 3.3, 6.1, 6.3, 7.1) are imported from external Gaussian-period or Schmidt-White evaluations, which is legitimate external support, not circularity. The self-citations [19] and [20] are used only for comparison and examples (Remark 3.4, Example 5.5), not as load-bearing premises, so they do not make the chain circular. The complement-spectrum multiplicity defect noted in the text is an error in Theorem 2.1 for disconnected complements, but an error is not a circular step; the connected cases used later are unaffected. Nothing in the claimed derivation reduces by construction to its own input.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted; the eigenvalues and weights are computed from fixed arithmetic formulas. The main uncharged input is the body of external Gaussian period and code weight results cited from [12] and [23]. The relation in Theorem 5.1 itself is derived from a character sum identity plus a cited weight formula, and no new particle, force, dimension, or other postulated entity is introduced.

assumptions (5)
  • standard math The spectrum of a Cayley graph on a finite abelian group is given by the character sums chi(S)
    Used in the proof of Theorem 2.1 to express graph eigenvalues as sums over the set R_k and to identify them with Gaussian periods.
  • domain assumption Gaussian period integrality: eta_i is an integer and N eta_i + 1 is congruent to 0 modulo p (Theorem 14 in [12])
    Imported from [12]; used to prove that the spectra are integral when k divides (q-1)/(p-1) in Theorem 2.1(b).
  • domain assumption The semiprimitive Gaussian period evaluations in Lemma 13 of [12] and the code weight formulas in Theorem 24 of [12] are correct for the stated (k,q)
    Used in Theorem 3.3 to give explicit semiprimitive spectra and in Section 5 to translate code weights into graph eigenvalues.
  • domain assumption The Schmidt-White exceptional weight formula (7.2) with the parameter table (7.3) is valid for the eleven exceptional pairs
    Used in Theorem 7.1 to compute weights and graph spectra for the exceptional pairs.
  • domain assumption The graph is simple, which requires k to divide (q-1)/2 when p is odd
    Stated after equation (1.1); the spectrum formulas apply to the undirected simple graph only under this condition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Spectral properties of generalized Paley graphs and their associated irreducible cyclic codes." pith.science (2026). https://pith.science/paper/XFKTF7JG

@misc{pith2026190808097,
  author       = {Pith},
  title        = {Pith review of: Spectral properties of generalized Paley graphs and their associated irreducible cyclic codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XFKTF7JG}},
  note         = {Machine review of arXiv:1908.08097}
}
abstract

For $q=p^m$ with $p$ prime and $k\mid q-1$, we consider the generalized Paley graph $\Gamma(k,q) = Cay(\mathbb{F}_q, R_k)$, with $R_k=\{ x^k : x \in \mathbb{F}_q^* \}$, and the irreducible $p$-ary cyclic code $\mathcal{C}(k,q) = \{(\textrm{Tr}_{q/p}(\gamma \omega^{ik})_{i=0}^{n-1})\}_{\gamma \in \mathbb{F}_q}$, with $\omega$ a primitive element of $\mathbb{F}_q$ and $n=\tfrac{q-1}{k}$. We first express the spectra of $\Gamma(k,q)$ in terms of Gaussian periods. Then, we show that the spectra of $\Gamma(k,q)$ and $\mathcal{C}(k,q)$ are mutually determined by each other if further $k\mid \tfrac{q-1}{p-1}$. We give $Spec(\Gamma(k,q))$ explicitly for those graphs associated with irreducible 2-weight cyclic codes in the semiprimitive and exceptional cases. We also compute $Spec(\Gamma(3,q))$ and $Spec(\Gamma(4,q))$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Supercharacters of finite abelian groups and applications to spectra of $U$-unitary Cayley graphs

    math.NT 2025-08 accept novelty 5.0 of 10

    A super-Cayley graph's spectrum is a super-Fourier transform of its connection set; for Frobenius rings this yields explicit spectral formulas and rationality criteria.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · cited by 1 Pith paper

  1. [12]

    C. Ding, J. Yang . Hamming weights in irreducible cyclic codes . Discrete Math. 313:4 (2013), 434–446

    work page 2013

  2. [1]

    Akhtar, T

    R. Akhtar, T. Jackson-Henderson, R. Karpman, M. Boggess, I. Jiménez, A. Kinzel, D. Pritikin. On the unitary Cayley graph of a finite ring . Electron. J. Comb. 16:1 (2009), RP 117, 13 pp

    work page 2009

  3. [2]

    Ananchuen

    W. Ananchuen . On the adjacency properties of generalized Paley graphs . Austral. J. Combin. 24 (2001), 129–147

    work page 2001

  4. [3]

    Baumer t, R.J

    L.D. Baumer t, R.J. McEliece . Weights of irreducible cyclic codes. Information and Control 20 (1972), 158–175

    work page 1972

  5. [4]

    Baumer t, J

    L.D. Baumer t, J. Mykkeltveit . Weight distributions of some irreducible cyclic codes. DSN Progr. Rep. 16 (1973), 128–131

    work page 1973

  6. [5]

    A.E. Brouwer . Strongly regular graphs’ page www.win.tue.nl/~aeb/graphs/srg/srgtab.html

    work page

  7. [6]

    Calderbank, W

    R. Calderbank, W. Kantor . The geometry of two-weight codes. Bull. London Math. Soc. 18 (1986) 97–122

    work page 1986

  8. [7]

    Cameron, J.H

    P.J. Cameron, J.H. v an Lint . Designs, graphs, codes and their links . Cambridge University Press, LMSST 22, 1991

    work page 1991

Show all 26 references
  1. [8]

    Delsar te

    P. Delsar te. Weights of linear codes and strongly regular normed spaces. Discrete Math. 3 (1972) 47–64

    1972

  2. [9]

    Delsar te, J.M

    P. Delsar te, J.M. Goethals . Irreducible binary cyclic codes of even dimension. Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Appl ications, Univ. North Carolina, Chapel Hill, NC, (1970) 100–113

    1970

  3. [10]

    C. Ding . The weight distribution of some irreducible cyclic codes. IEEE Trans. Inform. Theory 55:3 (2009), 955–960

    2009

  4. [11]

    C. Ding . A class of three-weight and four-weight codes . C. Xing, et al. (Eds.), Proc. of the Second International Workshop on Coding Theory and Cryptography. Lecture Notes in Computer Science, vol. 5557, Springer Verlag, (2009) 34–42

    2009

  5. [13]

    Ghinelli, J.D

    D. Ghinelli, J.D. Key, . Codes from incidence matrices and line graphs of Paley graph s. Adv. Math. Comm. 5 (2011), 93–108

    2011

  6. [14]

    Haemers, R

    W. Haemers, R. Peeters, J. v an Rijckevorsel . Binary codes of strongly regular graphs . Design Code. Cryptogr. 17 (1999), 187–209

    1999

  7. [15]

    J.D. Key, J. Limbupasiriporn . Partial permutation decoding for codes from Paley graphs . Cong. Numer. 170 (2004), 143–155

    2004

  8. [16]

    S. Li, S. Hu, T. Feng, G. Ge . The weight distribution of a class of cyclic codes related to Hermitian forms graphs. IEEE Trans. Inform. Theory 59:5 (2013), 3064–3067

    2013

  9. [17]

    T.K. Lim, C. Praeger . On Generalised Paley Graphs and their automorphism groups . Michigan Math. J. 58 (2009), 294–308

    2009

  10. [18]

    McEliece

    R.J. McEliece . Irreducible cyclic codes and Gauss sums . Combinatorics in: Proc. NATO Advanced Study Inst., Breukelen, 1974. Math. Centre Tracts 55, Math. Centrum, Amsterdam, 1974, 179–196

    1974

  11. [19]

    Podestá, D.E

    R.A. Podestá, D.E. Videla . The spectra of generalized Paley graphs and applications . arXiv:1812.03332, (2018). 22 RICARDO A. PODESTÁ, DENIS E. VIDELA

    2018 arXiv

  12. [20]

    Podestá, D.E

    R.A. Podestá, D.E. Videla . Weight distribution of cyclic codes defined by quadratic for ms and related curves. arXiv:1903.01838, (2019)

    2019 arXiv

  13. [21]

    Senevira tne, J

    P. Senevira tne, J. Limbupasiriporn . Permutation decoding from generalized Paley graphs . Appl. Algebra in Eng. Comm. and Computing 24 (2013) 225–236

    2013

  14. [22]

    Sharma, G.K

    A. Sharma, G.K. Bakshi . The weight distribution of some irreducible cyclic codes. Finite Fields Appl. 18:1 (2012), 144–159

    2012

  15. [23]

    Schmidt, C

    B. Schmidt, C. White . All two weight irreducible cyclic codes? Finite Fields Appl. 8 (2002), 1–17

    2002

  16. [24]

    J. H. v an Lint, A. Schrijver . Construction of strongly regular graphs, two-weight codes and partial geometries by finite fields . Combinatorica 1:1 (1981), 63–73

    1981

  17. [25]

    G. Vega, J. Wolfmann . New classes of 2-weight cyclic codes . Des. Codes Cryptogr. 42 (2007), 327–334

    2007

  18. [26]

    Z. Zhou, A. Zhang, C. Ding, M. Xiong . The weight enumerator of three families of cyclic codes . IEEE Trans. Inform. Theory 59:9 (2013), 6002–6009. Ricardo A. Podestá. F aMAF – CIEM (CONICET), Universidad Nac ional de Córdoba. A v. Medina Allende 2144, Ciudad Universitaria, (5...

    2013

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.