Certain Diagonal Equations and Conflict-Avoiding Codes of Prime Lengths
We study the construction of optimal conflict-avoiding codes (CAC) from a number theoretical point of view. The determination of the size of optimal CAC of prime length p and weight 3 is formulated in terms of the solvability of certain twisted Fermat equations of the form g^2 X^ℓ + g Y^ℓ + 1 = 0 over the finite field 𝔽_p for some primitive root g modulo p. We treat the problem of solving the twisted Fermat equations in a more general situation by allowing the base field to be any finite extension field 𝔽_q of 𝔽_p. We show that for q greater than a lower bound of the order of magnitude O(ℓ^2) there exists a generator g of 𝔽_q^× such that the equation in question is solvable over 𝔽_q. Using our results we are able to contribute new results to the construction of optimal CAC of prime lengths and weight 3.
READ FULL TEXT