Status of Gao's Conjecture

Question

In his 2001 paper titled "On The Deterministic Complexity of Factoring Polynomials", Shuhong Gao makes the following conjecture:

For any $a \in \mathbf{F}_q$ ($q$ is some prime power), we can write $a=\eta^u\theta$ where $\eta$ is a generator of the $2-sylow$ group ($q-1=2^ew$, $gcd(2,w)=1$). We can further expand $u$ as $u= u_0 2^{e-1}+u_1 2^{e-2}+...u_{e-1}$ with $u_i \in \{0,1\}$. Define $\sigma_2(a^2)=a$ ($\sigma_2$ is actually a square root algorithm they describe) if $u_0=0$ and $\sigma_2(a) = -a$ if $u_0=1$.

A set $F \subset \mathbf{F}_q$ is called square balanced if for each $\xi \in F$,

$|\{\zeta \in F : \zeta \neq \xi, \sigma_2((\xi-\zeta)^2)=\xi-\zeta\}|=\frac{n-1}{2}$.

Two sets $F_1, F_2 \subset \mathbf{F}_q$ are mutually square balanced if for each $\xi \in F_1$,

$|\{\zeta \in F_2 : \sigma_2((\xi-\zeta)^2)=\xi-\zeta\}|$ is the same for all $\xi \in F_1$, and similarly for $\xi \in F_2$ and $\zeta \in F_1$. Also for an integer $k$ define $F_k = \{a^k : a\in F\}$. Then a subset $F \subset \mathbf{F}_q$ is called super square balanced if:

1. $\forall 1 \le k \le (n\log{p})^6$, $F_k$ has cardinality $n$ and is square balanced.
2. All the sets $F_k$, $1 \le k \le (n\log{p})^6$, are pairwise disjoint.
3. All the sets $F_k$, $1 \le k \le (n\log{p})^6$ are mutually square balanced.

In his paper Gao conjectures that the conditions are too stringent for the existence of any square balanced sets in a finite field. If one is able to prove this then a direct implication would be a derandomization of polynomial factoring over finite fields (under the assumption of ERH). I was wondering if there has been any progress in proving/disproving this conjecture since it was made.

Answer 1

First of all, Gao's conjecture was that there does not exist a super square balanced set in a Finite field. Square balanced sets are known, in fact, Gao himself, in his paper, given an example of a family of square balanced polynomials.

There has been some additional work in 2008, by Chandan Saha and he gave an algorithm for factorization that works for all polynomials except a restricted class called cross-balanced polynomials. The conditions required for a polynomial to be cross-balanced appear to be stronger than super square balanced.