# Status of Gao's Conjecture

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.

-
I don't know. Only one paper in the Math Reviews database cites Gao's paper, and that was a survey paper. No review contains the phrase "square balanced". – Gerry Myerson Jul 3 '11 at 23:45