Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.