On the construction of small subsets containing special elements in a finite field
share
In this note we construct a series of small subsets containing a non-d-th power element in a finite field by applying certain bounds on incomplete character sums. Precisely, let h= q^δ>1 and d| q^h-1. Let r be a prime divisor of q-1 such that the largest prime power part of q-1 has the form r^s. Then there is a constant 0<ϵ<1 such that for a ratio at least q^-ϵ h of α∈F_q^hF_q, the set S={α-x^t, x∈F_q} of cardinality 1+q-1/M(h) contains a non-d-th power in F_q^ q^δ, where t is the largest power of r such that t<√(q)/h and M(h) is defined as M(h)=_r | (q-1) r^{v_r(q-1), _rq/2-_r h}. Here r runs thourgh prime divisors and v_r(x) is the r-adic oder of x. For odd q, the choice of δ=1/2-d, d=o(1)>0 shows that there exists an explicit subset of cardinality q^1-d=O(^2+ϵ'(q^h)) containing a non-quadratic element in the field F_q^h. On the other hand, the choice of h=2 shows that for any odd prime power q, there is an explicit subset of cardinality 1+q-1/M(2) containing a non-quadratic element in F_q^2. This improves a q-1 construction by Coulter and Kosick CK since _2(q-1)≤ M(2) < √(q). In addition, we obtain a similar construction for small sets containing a primitive element. The construction works well provided ϕ(q^h-1) is very small, where ϕ is the Euler's totient function.
READ FULL TEXT