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²X^ℓ+gY^ℓ+1=0 over the finite field F_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 F_q of F_p. We show that for q greater than a lower bound of the order of magnitude O(ℓ²) there exists a generator g of F_q^× such that the equation in question is solvable over F_q. Using our results we are able to contribute new results to the construction of optimal CAC of prime lengths and weight 3.