pith. sign in

arxiv: 2604.04126 · v1 · submitted 2026-04-05 · 🧮 math.NT · math.CO

Extensions of the Carlitz-McConnel and Blokhuis-Sziklai theorems for unions of cyclotomic classes

Maosheng Xiong , Chi Hoi Yip This is my paper

Pith reviewed 2026-05-13 16:56 UTC · model grok-4.3

classification 🧮 math.NT math.CO
keywords finite fieldsdifference quotientslinearized polynomialsCayley graphsmaximum cliquescyclotomic classespermutation polynomialsCarlitz-McConnel theorem
0
0 comments X

The pith

If a function's difference quotients stay in a union of cosets of a multiplicative subgroup over a finite field, then the function must be linearized plus a constant.

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

The paper extends the Carlitz-McConnel theorem, which classifies functions f over F_q whose difference quotients lie in a proper subgroup D of the multiplicative group as necessarily linearized polynomials of the form a x^{p^j} + b. It generalizes the setting to D being a union of cosets of a fixed subgroup, provided a mild assumption holds on the choice of D. A sympathetic reader would care because this gives a broader algebraic classification of functions that map field differences into restricted multiplier sets, directly tying into the structure of permutation polynomials. The same approach strengthens several earlier bounds on maximum clique sizes in the associated Cayley graphs over finite fields.

Core claim

Let p be prime and q = p^n. If D is a union of cosets of a fixed subgroup of F_q^*, and f : F_q to F_q satisfies (f(x) - f(y))/(x - y) in D for all x not equal to y, then under a mild assumption f must be of the form f(x) = a x^{p^j} + b for some a, b in F_q and integer j.

What carries the argument

The difference-quotient condition (f(x)-f(y))/(x-y) belonging to D, where D is a union of cosets of a subgroup of F_q^*; this algebraic restriction on pairwise slopes forces f to be additive-linearized.

If this is right

  • Such functions f are precisely the linearized polynomials under the stated assumption.
  • The result supplies new upper bounds or exact sizes for maximum cliques in the Cayley graphs whose connection sets are these unions of cosets.
  • Several earlier clique-size results of Blokhuis and Sziklai are recovered or improved as special cases.
  • The classification applies directly to questions about permutation polynomials whose normalized differences avoid certain residue classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The extension may yield new constructions of permutation polynomials whose difference quotients avoid prescribed cyclotomic classes.
  • Small-field exhaustive search could be used to test the precise boundary of the mild assumption and identify any exceptional cases.
  • The same coset-union technique might adapt to related problems on value sets or sum-product phenomena in finite fields.

Load-bearing premise

The unspecified mild assumption on the union of cosets that is needed to force the conclusion that f is linearized.

What would settle it

An explicit non-linearized function f over some F_q together with a qualifying union-of-cosets set D such that every difference quotient still lands in D.

read the original abstract

Let $p$ be a prime, let $q=p^n$, and let $D\subseteq \mathbb{F}_q^\ast$. A celebrated result of Carlitz and McConnel states that if $D$ is a proper subgroup of $\mathbb{F}_q^\ast$, and $f:\mathbb{F}_q\to\mathbb{F}_q$ is a function such that $(f(x)-f(y))/(x-y)\in D$ for all $x\neq y$, then $f$ must be of the form $f(x)=ax^{p^j}+b$. In this paper, we extend their result to the setting where $D$ is a union of cosets of a fixed subgroup of $\mathbb{F}_q^\ast$, under a mild assumption. In a similar spirit, we also investigate maximum cliques in related Cayley graphs over finite fields, strengthening several results of Blokhuis, Sziklai, and Asgarli and Yip.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript extends the Carlitz-McConnel theorem from the case where D is a proper subgroup of F_q^* to the case where D is a union of cosets of a fixed subgroup, under a mild assumption; it proves that any f: F_q → F_q satisfying (f(x)-f(y))/(x-y) ∈ D for all x ≠ y must be of the form f(x) = a x^{p^j} + b. It also strengthens several results on the size of maximum cliques in related Cayley graphs over finite fields, building on work of Blokhuis, Sziklai, Asgarli, and Yip.

Significance. If the derivations are correct and the mild assumption is both necessary and verifiable in the stated generality, the extension enlarges the class of admissible difference sets D while preserving the linearized conclusion, which is of interest in the theory of permutation polynomials and in extremal problems for Cayley graphs on additive groups of finite fields.

major comments (1)
  1. [Main theorem (after abstract) and its proof] The mild assumption required for the union-of-cosets extension (appearing in the statement of the main theorem after the abstract) is load-bearing for the claim that f must be linearized; the manuscript should explicitly state the assumption in the introduction, prove that it is strictly weaker than requiring D to be a subgroup, and supply a concrete counter-example showing that the conclusion fails when the assumption is dropped.
minor comments (2)
  1. [Section 2] Notation for the fixed subgroup and its cosets should be introduced once and used consistently; the current alternation between H and the index set is occasionally unclear.
  2. [Section 4] The strengthening of the Blokhuis-Sziklai clique bounds is stated only in the abstract; a short comparison table or explicit statement of the numerical improvement would help readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and valuable suggestions. We agree that the mild assumption plays a central role and will revise the manuscript to make its role clearer from the outset.

read point-by-point responses

  1. Referee: [Main theorem (after abstract) and its proof] The mild assumption required for the union-of-cosets extension (appearing in the statement of the main theorem after the abstract) is load-bearing for the claim that f must be linearized; the manuscript should explicitly state the assumption in the introduction, prove that it is strictly weaker than requiring D to be a subgroup, and supply a concrete counter-example showing that the conclusion fails when the assumption is dropped.

    Authors: We agree that the assumption is essential to the linearized conclusion and that its presentation can be improved. In the revised version we will move an explicit statement of the assumption into the introduction. We will also add a short subsection proving that the assumption is strictly weaker than the subgroup condition (by exhibiting a union of cosets that satisfies the assumption but is not a subgroup) and provide a concrete counter-example over a small finite field showing that the conclusion fails when the assumption is omitted. These additions will be placed immediately after the statement of the main theorem. revision: yes

Circularity Check

0 steps flagged

Minor self-citation not load-bearing; derivation remains self-contained

full rationale

The paper extends the external Carlitz-McConnel theorem to the case of D as a union of cosets of a fixed subgroup (under a mild assumption) and strengthens Blokhuis-Sziklai results on Cayley graph cliques. The cited prior work includes Asgarli-Yip, but this is not load-bearing for the central claims; the linearized form of f follows from the stated assumption and external theorems rather than reducing to a self-definition, fitted input renamed as prediction, or unverified self-citation chain. No equation or step in the derivation is equivalent to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard properties of finite fields and their multiplicative groups; no free parameters, ad-hoc axioms, or invented entities are indicated in the abstract.

axioms (1)
  • standard math F_q is a finite field with q = p^n elements and F_q^* is its multiplicative group
    Basic setup of the Carlitz-McConnel theorem and all related statements.

pith-pipeline@v0.9.0 · 5474 in / 1123 out tokens · 31953 ms · 2026-05-13T16:56:16.993862+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Aguglia, B

    A. Aguglia, B. Csajb ´ok, and Z. Weiner. Intersecting families of graphs of functions over a finite field.Ars Math. Contemp., 24(1):Paper No. 4, 22, 2024

    work page 2024

  2. [2]

    Asgarli and C

    S. Asgarli and C. H. Yip. Van Lint–MacWilliams’ conjecture and maximum cliques in Cayley graphs over finite fields.J. Combin. Theory Ser. A, 192:Paper No. 105667, 23, 2022

    work page 2022

  3. [3]

    S. Ball. The number of directions determined by a function over a finite field.J. Combin. Theory Ser. A, 104(2):341–350, 2003

    work page 2003

  4. [4]

    Blokhuis

    A. Blokhuis. On subsets ofGF(q 2)with square differences.Nederl. Akad. Wetensch. Indag. Math., 46(4):369– 372, 1984

    work page 1984

  5. [5]

    Blokhuis, S

    A. Blokhuis, S. Ball, A. E. Brouwer, L. Storme, and T. Sz˝onyi. On the number of slopes of the graph of a function defined on a finite field.J. Combin. Theory Ser. A, 86(1):187–196, 1999

    work page 1999

  6. [6]

    Blokhuis, A

    A. Blokhuis, A. Seress, and H. A. Wilbrink. Characterization of complete exterior sets of conics.Combinatorica, 12(2):143–147, 1992

    work page 1992

  7. [7]

    Bruen and B

    A. Bruen and B. Levinger. A theorem on permutations of a finite field.Canadian J. Math., 25:1060–1065, 1973

    work page 1973

  8. [8]

    L. Carlitz. A theorem on permutations in a finite field.Proc. Amer. Math. Soc., 11:456–459, 1960

    work page 1960

  9. [9]

    Csajb ´ok

    B. Csajb ´ok. Extending a result of Carlitz and McConnel to polynomials which are not permutations.Finite Fields Appl., 108:Paper No. 102683, 6, 2025

    work page 2025

  10. [10]

    Feng and K

    T. Feng and K. Momihara. Three-class association schemes from cyclotomy.J. Combin. Theory Ser. A, 120(6):1202–1215, 2013

    work page 2013

  11. [11]

    Feng and Q

    T. Feng and Q. Xiang. Strongly regular graphs from unions of cyclotomic classes.J. Combin. Theory Ser. B, 102(4):982–995, 2012

    work page 2012

  12. [12]

    Goryainov and C

    S. Goryainov and C. H. Yip. Extremal Peisert-type graphs without the strict-EKR property.J. Combin. Theory Ser. A, 206:Paper No. 105887, 42, 2024

    work page 2024

  13. [13]

    Green and I

    B. Green and I. Z. Ruzsa. Freiman’s theorem in an arbitrary abelian group.J. Lond. Math. Soc. (2), 75(1):163– 175, 2007

    work page 2007

  14. [14]

    Grundh ¨ofer

    T. Grundh ¨ofer. ¨Uber Abbildungen mit eingeschr ¨anktem Differenzenprodukt auf einem endlichen K ¨orper.Arch. Math. (Basel), 37(1):59–62, 1981

    work page 1981

  15. [15]

    G. A. Jones. Paley and the Paley graphs. InIsomorphisms, symmetry and computations in algebraic graph theory, volume 305 ofSpringer Proc. Math. Stat., pages 155–183. Springer, Cham, 2020

    work page 2020

  16. [16]

    Knarr and M

    N. Knarr and M. Stroppel. Polarities and unitals in the Coulter-Matthews planes.Des. Codes Cryptogr., 55(1):9– 18, 2010

    work page 2010

  17. [17]

    H. W. Lenstra, Jr. Automorphisms of finite fields.J. Number Theory, 34(1):33–40, 1990

    work page 1990

  18. [18]

    T. K. Lim and C. E. Praeger. On generalized Paley graphs and their automorphism groups.Michigan Math. J., 58(1):293–308, 2009

    work page 2009

  19. [19]

    Lov ´asz and A

    L. Lov ´asz and A. Schrijver. Remarks on a theorem of R´edei.Studia Sci. Math. Hungar., 16(3-4):449–454, 1983

    work page 1983

  20. [20]

    Martin and C

    G. Martin and C. H. Yip. Distribution of power residues over shifted subfields and maximal cliques in generalized Paley graphs.Proc. Amer. Math. Soc., 153(1):109–124, 2025

    work page 2025

  21. [21]

    McConnel

    R. McConnel. Pseudo-ordered polynomials over a finite field.Acta Arith., 8:127–151, 1962/63

    work page 1962

  22. [22]

    N. Mullin. Self-complementary arc-transitive graphs and their imposters, 2009. Master’s thesis, University of Waterloo

    work page 2009

  23. [23]

    M. E. Muzychuk. Automorphism groups of Paley graphs and cyclotomic schemes. InIsomorphisms, symmetry and computations in algebraic graph theory, volume 305 ofSpringer Proc. Math. Stat., pages 185–194. Springer, Cham, 2020

    work page 2020

  24. [24]

    P. Sziklai. On subsets ofGF(q 2)withdth power differences.Discrete Math., 208/209:547–555, 1999

    work page 1999

  25. [25]

    T. Tao. The sum-product phenomenon in arbitrary rings.Contrib. Discrete Math., 4(2):59–82, 2009

    work page 2009

  26. [26]

    J. H. van Lint and F. J. MacWilliams. Generalized quadratic residue codes.IEEE Trans. Inform. Theory, 24(6):730–737, 1978

    work page 1978

  27. [27]

    D. Wan. Generators and irreducible polynomials over finite fields.Math. Comp., 66(219):1195–1212, 1997

    work page 1997

  28. [28]

    Q. Xiang. Cyclotomy, Gauss sums, difference sets and strongly regular Cayley graphs. InSequences and their applications—SETA 2012, volume 7280 ofLecture Notes in Comput. Sci., pages 245–256. Springer, Heidelberg, 2012

    work page 2012

  29. [29]

    C. H. Yip. Erd ˝os-Ko-Rado theorem in Peisert-type graphs.Canad. Math. Bull., 67(1):176–187, 2024. 11

    work page 2024

  30. [30]

    C. H. Yip. A strengthening of McConnel’s theorem on permutations over finite fields.Canad. Math. Bull., 68(1):213–218, 2025

    work page 2025

  31. [31]

    C. H. Yip. Van Lint–MacWilliams’ conjecture and maximum cliques in Cayley graphs over finite fields, II.J. Combin. Theory Ser. A, 221:Paper No. 106162, 2026. DEPARTMENT OFMATHEMATICS, THEHONGKONGUNIVERSITY OFSCIENCE ANDTECHNOLOGY, HONG KONG, P. R. CHINA Email address:mamsxiong@ust.hk SCHOOL OFMATHEMATICS, GEORGIAINSTITUTE OFTECHNOLOGY, GA 30332, UNITEDSTA...

    work page 2026