Paley cliques and nonpolynomial counts of totally positive matrices
Henry Zweiman
September 9, 2026
Abstract
An element of a finite field is positive if it is a nonzero square, and a matrix is totally positive if all its minors are positive. We determine the number of totally positive two-by-three matrices over every finite field. For a fixed prime , this count is polynomial in the field size on residue classes of the extension degree if and only if or . For every prime , no polynomial formula holds even eventually on any arithmetic progression of extension degrees. This disproves the quasipolynomial-type conjecture of Ayyer and Prasad in the smallest possible number of matrix entries. The proof reduces two-row total positivity to Paley clique counts and uses the known four-clique formula of Dawsey and McCarthy. We identify the surviving Gaussian exponential terms and the exact minimal recurrence of order seventeen.
1. Introduction and results
Let . Following the finite-field positivity convention used in [1], call the elements of positive. For positive integers , let consist of the matrices all of whose square minors belong to . Rows and columns in a minor retain their natural order. In particular all entries must be nonzero squares. Write
Ayyer and Prasad [1, Conjecture 5.12] ask whether, for each prime and pair , there is a positive integer and rational polynomials of degree such that
Their structural formula from zeta-function rationality is a finite sum of powers of algebraic numbers. The additional restriction in (1) is much stronger. The distinction already matters for two-by-three matrices.
Theorem 1.
For every prime power ,
In the last line, write with even, choosing when . When and is even, take . The value of is determined by these conditions.
Theorem 2.
Fix a prime . The sequence has polynomial formulas in on finitely many residue classes of if and only if
If , then for every and there is no polynomial such that
for all sufficiently large integers . Thus (1) fails for and every such prime, including .
Corollary 3.
Six is the smallest number of entries in a matrix size for which Conjecture 5.12 of [1] can fail. Both sizes and exhibit failure.
Our proof also identifies the minimal constant-coefficient recurrence. If , choose with odd and nonzero and even, and put
Theorem 4.
For , the sequence has minimal constant-coefficient recurrence over of order seventeen. Its characteristic polynomial is
Every arithmetic-progression subsequence also has minimal recurrence order seventeen.
The four-clique evaluation used below is an existing result [2, Corollary 2.3], extending work of Evans, Pulham, and Sheehan. We do not claim a new Paley clique formula. The contribution is its connection to total positivity and the resulting exact characteristic-dependent obstruction to the proposed polynomial form. The complete count, counterexample, and recurrence are consequences of this one connection. We make no claim here about the separate positive-semidefinite counting conjecture in [1, Conjecture 4.31].
2. Two rows and Paley graphs
The normalization underlying our argument works for any number of columns.
Proposition 5.
Let . Then equals times the number of ordered tuples satisfying
If and denotes the number of unordered -vertex cliques in the Paley graph, then
Proof.
Write the columns of the matrix as . Its entries are positive exactly when and . The minor in columns is
Since is a nonzero square, positivity is equivalent to (5). Each admissible tuple has exactly choices of the first row.
For , minus one is a square, so adjacency in is symmetric. The tuple condition says precisely that is an ordered clique. There are ordered cliques altogether. Translating the first vertex to zero is a bijection between ordered cliques with any prescribed first vertex and those with first vertex zero. Division by gives (6).
For even , the set is all of . The tuple condition simply requires distinct nonzero entries, and hence
When , the product contains a zero factor, as it should. This recovers the characteristic-two formula in [1, Section 5.1].
3. The exact two-by-three count
We first dispose of the directed case with an elementary character sum.
Lemma 6.
Suppose . In the tournament whose vertices are and whose arrows point from to when , every vertex has outdegree .
Proof.
Let be the quadratic character, with . For a fixed , division by reduces its outdegree to the number of such that . Excluding , this is
The two linear character sums here are and . Also
To see the last identity directly, the number of solutions of is plus that sum. The substitution , turns the equation into , which has exactly solutions since the characteristic is odd. The outdegree is therefore . Since , exactly one of the two possible arrows occurs between any two distinct vertices.
For even , apply (7) with . For , the normalized tuples in Proposition 5 are the transitive triples in the tournament of Lemma 6, with their unique forward ordering. Every such triple has a unique source. A vertex has outgoing neighbors, and each unordered pair of those neighbors gives one transitive triple with that source. The number of tuples is
Multiplication by gives the second line of (2). The formula also applies at , where the count is zero.
with exactly the representation conditions on in the theorem. Substituting (8) in (6), and using , gives the last line of (2).
The distinction between a prime field and a prime-power field is essential in (8). For split primes the condition selects the primitive Gaussian representation; choosing an arbitrary representation of as two squares can give an incorrect count.
4. Extension degrees and nonpolynomiality
Fix and use (3). The Gaussian integers form a unique factorization domain, and and are nonassociate primes above . Write
Then is odd, is even, and . Moreover : modulo the Gaussian prime , the equality
has a nonzero right-hand side. Thus this is an admissible representation in Theorem 1. With
we obtain the exact formula
In particular,
Lemma 7.
Neither nor is a root of unity.
Proof.
We have . If a positive power of this quotient were one, unique factorization would equate positive powers of the distinct Gaussian primes and . This is impossible. The second quotient is , so it is not torsion either.
We use a standard elementary independence fact: if are distinct nonzero complex numbers, then the sequences are linearly independent, even when restricted to all sufficiently large . Indeed consecutive equations give a Vandermonde matrix, multiplied by a nonsingular diagonal matrix.
When , the first line of (2) is a polynomial of degree six. When , the odd and even extension degrees have respectively the polynomials
Now suppose . Expanding (9) expresses as a sum of powers with bases
The seven coefficients in the first group, in increasing order of powers of , are
Each coefficient in the second group is , so all seventeen coefficients are nonzero.
These bases remain pairwise distinct after taking any positive integral power . Distinct absolute values separate different values of in the second group. For a fixed , the two conjugate bases cannot acquire equal -th powers by Lemma 7. A base from the second group cannot acquire the same -th power as any : equality of absolute values would give , and equality of values would force or its conjugate. The bases in the first group are already distinct positive reals.
On restricting to , every coefficient is multiplied by the nonzero -th power of its base, and every base is replaced by its -th power. A polynomial in is a linear combination only of sequences with bases , . Subtracting it from the expansion leaves nonzero coefficients at all ten bases from the second group. The independence fact above rules out eventual equality. This proves the stated stronger failure on every progression.
If , then either , , or . A one-row or one-column count is , which is polynomial in for each characteristic. The two-by-two counts, also given in [1, Section 5.1], are
They follow by the same normalization and the count of simultaneous squares . For each fixed prime these formulas have period at most two in the extension degree. Theorem 2 supplies the six-entry counterexample. Transposition preserves all minors and gives the other orientation.
A sequence is annihilated by the shift operator minus . Thus the expansion with bases (11) is annihilated by the product of these seventeen linear factors. Pairing conjugate factors gives (4), since .
Conversely, if a polynomial in the shift operator annihilates the sequence, applying it to the expansion multiplies the coefficient at each base by . Independence and nonzero coefficients force to vanish at all seventeen distinct bases. Hence its degree is at least seventeen. The product in (4) has rational, indeed integer, coefficients, proving minimality over . The same argument applies to every progression, using the noncollision proof in Theorem 2.
For the simplest prime , take , so and
The initial matrix counts are
The general proof does not infer nonpolynomiality from these initial values. It identifies bases that cannot become powers of after any finite periodic restriction.
The generating function of is rational, as the zeta-function approach in [1] predicts. The obstruction is the presence of the ten bases and , rather than a failure of rationality. More generally, whenever a counting sequence is given as a finite sum of exponentials, one must group bases whose ratios are roots of unity before testing for polynomial behavior on progressions. A surviving base outside the powers of times roots of unity prevents the proposed form. Here the arithmetic of split Gaussian primes verifies that no such cancellation occurs.
The correspondence (6) also relates wider two-row matrices to larger Paley cliques. It offers a way to transfer counting information and existence bounds between the two problems. Exact higher-column formulas and the separate semidefinite conjecture are not settled in this paper.
Preparation and verification
This manuscript was prepared with OpenAI Codex assistance in problem selection, proof development, literature checking, computation, and writing. The originating agent performed the internal audit; no human referee or separate-agent review is claimed. The accompanying assessment records the priority-search limits and credits the existing clique formula. Optional finite checks in 29 prime and extension fields, including direct enumeration of the original six entries over nine small fields, agree with the formulas. The general nonpolynomiality and minimality arguments are proofs independent of these finite checks.
References
[1] A. Ayyer and S. Prasad, Positive definite, positive semidefinite and totally positive matrices over finite fields, arXiv:2608.17702v1 (2026). arXiv:2608.17702v1.
[2] M. L. Dawsey and D. McCarthy, Generalized Paley graphs and their complete subgraphs of orders three and four, Research in the Mathematical Sciences 8, article 18 (2021). arXiv:2006.14716.