REVIEW
Conflict-avoiding codes and near-primitive roots
Number Theory · Submitted 5 Oct 2026 · 45 references
Pith's verdict: Solid, honest extension of Wagstaff's framework to a coding-theoretic quantity; the numerical constants are the only real soft spot.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
The primes where a code-theoretic quantity O(p) equals k follow an Artin-type density law.
The reading
What carries the argument
The central object is O(n), the number of odd-length cycles in the graph G_n whose vertices are nonzero residues modulo n up to sign and whose edges are b ≡ ±2a (mod n); the graph decomposes into disjoint cycles, and a loop arises exactly when 3 | n. For prime n the squaring map gives an isomorphism G_p ≅ H_p, where H_p has the nonzero squares as vertices and edges b ≡ 4a, so each cycle has length ord_p(4) and O(p) = [(F_p^×)^2 : ⟨4⟩] = [F_p^× : ⟨−1,2⟩]. The distributional work runs through the Artin-type density δ_g(t) for primes with ord_p(g) = (p−1)/t, which is available under GRH; the density δ_k is obtained by subtracting two applications of the published near-primitive-root density, while the unconditional statements come from the elementary density of primes with 2 | ord_p(4) applied to the completely multiplicative set of integers built from that prime set.
Extended reading notes
Core claim
The central claim is that the level sets of the code-theoretic quantity O(p) are governed by the near-primitive-root theory of the number 4. Precisely, for an odd prime p, O(p) equals the index [F_p^× : ⟨−1,2⟩], which is one half of ind_p(4) when ord_p(4) is odd and 0 otherwise; the underlying graph G_p is isomorphic to the square graph H_p whose cycles all have length ord_p(4). Assuming GRH, the primes with O(p)=k have natural density δ_k = A·E(k) for odd k, density 0 for k≡2 (mod 4), and density (2/3)·A·E(k) for 4|k, with A the Artin constant and E(k) the explicit Euler-product factor of the paper, and the counting function P_k(x) has main term δ_k·x/log x. Beyond primes, the paper proves P(x) = (5/12)·x/log x + O(x log log x/(log x)^{7/6}) for the number of primes admitting a tight equi-difference code, and N_0(x) = C0·x/(log x)^{7/12} for the odd integers with O(m)=0, with C0 = 0.32235..., determined numerically by truncating an Euler product at t = $10^{11}$. When O(p) is itself an odd prime, the upper bound M(p) ≤ M_e(p) + ⌊O(p)/3⌋ is attained, and such primes, still under GRH, have relative density 0.508822711238... among primes with O(p) > 2.
Load-bearing premise
The prime-level densities δ_k for k≥1 are established only under the Generalized Riemann Hypothesis, which is assumed so that the relevant Dedekind zeta-functions have all nontrivial zeros on the critical line; the stated δ_k arises by subtracting two GRH-dependent near-primitive-root densities, and a secondary fragility is that the constant C0 = 0.32235... in Theorem 5 is evaluated by truncating an Euler product at t = $10^{11}$ without a proved bound on the discrepancy.
Editorial extensions
If this is right
- Tight equi-difference conflict-avoiding codes of prime length exist for a set of primes of natural density 5/12, and the count of such primes is P(x) = (5/12)·x/log x + error.
- For every k≡2 (mod 4) there are no primes at all with O(p)=k, a statement that holds unconditionally from quadratic reciprocity.
- For each fixed e≥1, there are at least comparable-many odd integers with O(m)=e, the count Ne(x) being ≫_e x/(log x)^{7/12}.
- When O(p) is an odd prime, the optimal code size M(p) equals M_e(p) + ⌊O(p)/3⌋, so those primes realize the maximum possible gain over equi-difference codes.
- The same techniques give uniform densities for the level sets of O(p) inside prescribed arithmetic progressions, with explicit rational forms for k=0 and k=1.
Reading between the lines
- If the density formula were confirmed numerically for several values of k across increasing ranges of x, the ratio of counted primes with O(p)=k to x/log x should stabilize at δ_k; a stable match would be a strong check that the GRH-based subtraction of the two near-primitive-root densities is the right decomposition.
- The paper's characterization of O(p)=0 by the base-4 digit mean of 1/p being 3/2 offers a completely independent, non-order-theoretic test of the level sets, since one can estimate digit means directly from data without computing orders.
- The constant C0 = 0.32235... rests on truncating an Euler product at t = 10^11 with a numerical confirmation but no proved remainder bound; a provable error estimate would convert the stated value into a certified interval.
- The graph-isomorphism route suggests that the same index-type identity might be pushed to prime powers or to other bases g, where the order-condition analysis would similarly reduce O to a near-primitive-root density.
Original abstract
An important role in the theory of conflict-avoiding codes is played by a quantity involving the multiplicative order of $4$ modulo $d$, with $d$ running over all positive divisors of an odd integer $n$. We establish results on its distribution as $n$ varies over the odd prime numbers, respectively odd integers, using techniques from the study of Artin's primitive root conjecture. We also point out some other interpretations of this quantity, with one of them making a connection with the factorization of $X^n-1$ into irreducibles over the finite field $\mathbb F_2$.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
An important role in the theory of conflict-avoiding codes is played by a quantity involving the multiplicative order of $4$ modulo $d$, with $d$ running over all positive divisors of an odd integer $n$. We establish results on its distribution as $n$ varies over the odd prime numbers, respectively odd integers, using techniques from the study of Artin's primitive root conjecture. We also point out some other interpretations of this quantity, with one of them making a connection with the factorization of $X^n-1$ into irreducibles over the finite field $\mathbb F_2$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | An important role in the theory of conflict-avoiding codes is played by a quantity involving the multiplicative order of $4$ modulo $d$, with $d$ running over all positive divisors of an odd integer $n$. | background 1.00 | 0.08 | 0.08 | asserted 1.00 |
| s1 | We establish results on its distribution as $n$ varies over the odd prime numbers, respectively odd integers, using techniques from the study of Artin's primitive root conjecture. | contribution 0.93 | 0.95 | 0.58 | asserted 1.00 |
| s2 | We also point out some other interpretations of this quantity, with one of them making a connection with the factorization of $X^n-1$ into irreducibles over the finite field $\mathbb F_2$. | interpretation 0.88 | 0.82 | 0.08 | asserted 0.93 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.