Improved lower bounds for Sárközy's theorem in function fields from independent sets in products of generalized Paley graphs

Let Pq,n be the set of polynomials of degree < n over F_q and let k ≥ 2. Naslund proved that Pq,n contains a subset of size rk,2(F_q)n/2k qn(1−1/k) with no two elements differing by a nonzero k-th power, where rk,2(F_q) is the independence number of the strong square of the generalized Paley graph Paley_k(F_q), and instantiated this with rk,2(F_q) ≥ q and, for k = 3, with r3,2(F_7) = 10. We determine r3,2(F_13) = 21 by two independent exhaustive computations, which gives a set of size |P13,n|^c with c = 2/3 + log 21/(6 log 13) = 0.864495…, the largest exponent this method has produced for cube differences and an improvement over Naslund's q5n/6 at q = 13. We exhibit an infinite family of exactly computable cases: whenever the nonzero k-th powers of F_q form the multiplicative group of a subfield Fq′ with [F_q : Fq′] = d, one gets sets of size qn(1−1/dk), which beats qn(1−1/2k) as soon as d ≥ 3. Finally, explicit verified independent sets give r4,2(F_17) ≥ 41 and r7,2(F_29) ≥ 139, hence exponents 0.913841… for fourth powers over F_17 and 0.961815… for seventh powers over F_29, compared with 0.875 and 0.928571… previously. All certificates are verified exhaustively by a standalone script included in the paper.