1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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". $\endgroup$ Jul 3, 2011 at 23:45

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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