When Are Monomial Digraphs Over Prime Fields Isomorphic?

A unit multiplier decides isomorphism over prime fields

For a prime power q and positive integers m and n, the monomial digraph D(q;m,n) has vertex set F_q × F_q, and an arc from (x1,x2) to (y1,y2) exactly when x2 + y2 = x1^m · y1^n. Every such digraph has q² vertices, q³ arcs, in-degree and out-degree q at every vertex, and a loop at (0,0).

Earlier work proved one direction: if there is an integer k coprime to q−1 with m2 ≡ k·m1 and n2 ≡ k·n1 modulo q−1, then D(q;m1,n1) and D(q;m2,n2) are isomorphic. Kodess and Lazebnik conjectured the converse. This paper proves that converse when q is prime, so over prime fields the multiplier condition is necessary as well as sufficient.

The multiplier is not arbitrary. It must be relatively prime to q−1, and both congruences are taken modulo q−1. That single integer k simultaneously rescales m and n, which is why the criterion is about the pair (m,n) rather than about m or n separately.

Extension fields admit isomorphic pairs with no such multiplier

The conjecture is false in general. The paper records that D(25;3,6) and D(25;3,18) are isomorphic, yet no integer k satisfies (3,18) ≡ k·(3,6) modulo 24. The authors also acknowledge a previously mistaken computation in their earlier work that overlooked this pair.

This is not an isolated accident. Theorem 2 builds an infinite family: for any odd prime power R ≡ 1 mod 4, with q = R² and m = (R+1)/2, the three digraphs D(q;m,2m), D(q;m,2m²) and D(q;m²,2m) are mutually isomorphic, while no integer k maps (m,2m) to (m,2m²) or to (m²,2m).

The smallest member is q = 25, where R = 5, a = (R−1)/2 = 2, m = 3 and n = 6, giving D(25;3,6) ≅ D(25;3,18) ≅ D(25;9,6). Each of these digraphs has 625 vertices and 15625 arcs. So the prime-field criterion is a genuine boundary, not a general theorem about all finite fields.

Normalizing the isomorphism and forcing it to be linear

The proof of Theorem 1 first reduces to the case m1 ≠ n1, since m1 = n1 is handled by earlier results. Necessary conditions from prior work give m2 = m1 and n2 = n1, where x denotes gcd(x, q−1). Passing to converse digraphs if needed lets the authors assume m1 ≤ n1.

An isomorphism can then be written as φ(x,y) = (f(x,y), g(y)) with a normalized form sending (0,0) to (0,0) and (1,0) to (1,0). The technical heart is showing g is linear, i.e. g(z) = λz for some nonzero λ in F_p. The argument studies how g acts on cosets of the subgroup A of n1-th powers, shows g is an automorphism of a nontrivial Cayley digraph Cay(F_p, A), and invokes the classical result that the automorphism group of such a prime-degree Cayley digraph embeds in the affine group AGL1(F_p).

From there the proof strengthens the identities to g(z) = z, f(x,y)^m2 = x^m1 and f(x,y)^n2 = x^n1 for all x, y, z in F_p. Setting F(x) = f(x,0) yields a permutation of F_p with F(x)^m2 = x^m1 and F(x)^n2 = x^n1, and a separate lemma converts exactly that permutation into the required multiplier k coprime to q−1. The case n1 = 1 is handled by a different route: two distinct vertices have disjoint in-neighborhoods precisely when their first coordinates agree, which forces the first coordinate of φ to depend only on x, after which additivity of g gives g(z) = z.

A basis swap over the subfield builds the counterexamples

Theorem 2 is constructive rather than merely existential. With R an odd prime power congruent to 1 mod 4, q = R², m = (R+1)/2 and a = (R−1)/2, the authors take a primitive element α of F_q and set β = α^m. Because q−1 = 4am, β has order 4a = 2(R−1), so β lies outside F_R while β² generates F_R^×; hence {1, β} is a basis of F_q over F_R.

The isomorphism is assembled from two maps. An invertible F_R-linear map T sends 1 to β^{3a} and β to β, which is a basis swap; a companion permutation σ on F_q is defined by σ(α^j) = α^{j+s(j)}, with s(j) = a for even j and 2a for odd j. Since a is even, j ↦ j + s(j) preserves parity and acts as a translation on each parity class of Z_{q−1}, so σ is a bijection. The identity T(x^m y^{2m}) = σ(x)^m σ(y)^{2m²} then makes φ(x,y) = (σ(x), T(y)) an isomorphism from D(q;m,2m) to D(q;m,2m²).

The third isomorphism, D(q;m,2m) ≅ D(q;m²,2m), comes from the sufficient direction instead: k = m + 4a is coprime to 4a and satisfies k(m,2m²) ≡ (m²,2m). The nonexistence half is a short congruence obstruction. Every scalar multiple (u,v) of (m,2m) has v ≡ 2u, but 2m² − 2m = 2m(m−1) = 2ma = (q−1)/2, which is not 0 modulo q−1, so no multiplier can produce either target pair.

Nonprime fields and algorithmic detection stay unresolved

The paper is explicit about what it does not settle. For prime powers that are not primes, Theorem 2 shows the multiplier condition is not necessary, but the general classification of which parameter pairs give isomorphic monomial digraphs over nonprime finite fields remains open.

Two further questions are posed without resolution. The first asks whether a finite family H of digraphs exists such that, for sufficiently large prime power q and all parameter pairs, equality of the subdigraph counts n(H,D1) = n(H,D2) for every H in H would force D1 ≅ D2; the authors state they have not been able to find such a family. The second asks for a polynomial-time algorithm in q that decides whether D1 and D2 are isomorphic.

These are stated as open problems, not as results, and they should be read that way: the paper's proven contribution is the prime-field criterion plus the extension-field counterexample family.

Check primality before applying the multiplier test

The practical split in this paper is between q prime and q a nonprime prime power. If q is prime, the multiplier test is decisive in both directions: compute m1 = gcd(m1, q−1), n1 = gcd(n1, q−1), m2 = gcd(m2, q−1), n2 = gcd(n2, q−1), and the digraphs are isomorphic exactly when a single k coprime to q−1 rescales (m1,n1) into (m2,n2) modulo q−1.

If q is not prime, a failure to find such a k proves nothing. The family in Theorem 2 gives concrete witnesses: whenever R is an odd prime power with R ≡ 1 mod 4, q = R² and m = (R+1)/2, the pairs (m,2m), (m,2m²) and (m²,2m) are pairwise linked by isomorphisms even though no admissible multiplier relates them. The smallest instance, q = 25 with m = 3, is the one to keep in mind as the counterexample to any blanket use of the criterion.

The most decision-relevant point is therefore the scope condition itself: the necessary-and-sufficient multiplier criterion is a theorem about prime fields, and the extension-field counterexamples show that extending it beyond that setting is not a matter of missing a proof but of a false statement.

Sources used in this answer