7
$\begingroup$

Let $m\geq4$ be an even integer, $V\subset\mathbb{C}^{m-1}$ be the solution set of the following polynomial equations: \begin{cases} &\sum\limits_{s=1}^{2t-1}z_sz_{2t-s}+\sum\limits_{s=2t+1}^{m-1}z_sz_{m+2t-s}=0,\quad t=1,\dots,m/2-1,\\ &z_sz_{\frac{m}{2}+s}=0,\quad s=1,\dots,m/2-1,\\ &z_sz_{m-s}=0,\quad s=1,\dots,m/2. \end{cases} For convenience, denote the left hand side of the $t$th equation by $f_t$. Note that the last equation implies that $z_{\frac{m}{2}}=0$.

Question: Is $V$ zero-dimensional?

Remark 1: Since the above equations are homogenous, this is equivalent to ask if $V$ only contains $0\in\mathbb{C}^{m-1}$. Computation via Groebner basis shows that it s ture for $m\leq18$.

Remark 2: If the indices are counted modulo $m$, then the system (with solution $(z_0,z_1,\dots,z_{m-1})\in\mathbb{C}^m$ but $z_0$ always zero, so in one-to-one correspondence with the solution $(z_1,\dots,z_{m-1})\in\mathbb{C}^{m-1}$ of our original system) can be written shorter as \begin{cases} &\sum\limits_{s=0}^{m-1}z_sz_{2t-s}=0,\quad t=1,\dots,m/2-1,\\ &z_sz_{\frac{m}{2}+s}=0,\quad s=1,\dots,m/2-1,\\ &z_sz_{m-s}=0,\quad s=0,\dots,m/2. \end{cases}

When $m=4$, the system is \begin{cases} &z_1^2+z_3^2=0,\\ &z_1z_3=0,\\ &z_2=0. \end{cases} Observing that the first two equations lead to $z_1=z_3=0$, we know the answer is true for $m=4$.

When $m=6$, the system is \begin{cases} &z_1^2+2z_3z_5+z_4^2=0,\\ &2z_1z_3+z_2^2+z_5^2=0,\\ &z_1z_4=z_2z_5=0,\\ &z_1z_5=z_2z_4=0,\\ &z_3=0 \end{cases} Substituting $z_3=0$ into the first equation we get $z_1^2+z_4^2=0$, which in conjunction with $z_1z_4=0$ implies $z_1=z_4=0$. We deduce similarly that $z_2=z_5=0$, so the answer is true for $m=6$.

When $m=8$, the system is \begin{cases} &z_1^2+2z_3z_7+2z_4z_6+z_5^2=0,\\ &2z_1z_3+z_2^2+2z_5z_7+z_6^2=0,\\ &2z_1z_5+2z_2z_4+z_3^2+z_7^2=0,\\ &z_1z_5=z_2z_6=z_3z_7=0,\\ &z_1z_7=z_2z_6=z_3z_5=0,\\ &z_4=0 \end{cases} We get from the first equation and $z_3z_7=z_4=0$ that $z_1^2+z_5^2=0$, so $z_1=z_5=0$ as $z_1z_5=0$. We get from the third equation and $z_1z_5=z_4=0$ that $z_3^2+z_7^2=0$, so $z_3=z_7=0$ as $z_3z_7=0$. Then the second equation turn out to be $z_2^2+z_6^2=0$, so $z_2=z_6=0$ as $z_2z_6=0$. This shows that the answer is true for $m=8$.

When $m=10$, we are not lucky enough to simply apply the argument like above. However, I think exhaustivity of "the possible zeros" between $z_1,\dots,z_9$ should work. Here "the possbile zeros" means assigning zeros to some of the $z_k$'s such that

(i) for $s=1,\dots,4$, at least one of $z_s$ and $z_{5+s}$ is zero,

(ii) for $s=1,\dots,4$, at least one of $z_s$ and $z_{10-s}$ is zero,

(iii) $z_5$ is zero,

and then figure out if this implies all of the $z_k$'s are zero. For example, we start with supposing $z_1=z_2=z_3=z_4=z_5=0$, then first deduce $z_6=0$ and $z_9=0$ and next $z_7=0$ and $z_8=0$. If it can be shown that with any initial assignment of zeros satisfying (i)-(iii) we will succesfully deduce all the $z_k$'s are zero, then the answer for $m=10$ is true. This may hopefully lead to a more efficient algorithm for our system than using Groebner basis method.

Edit: My attempt to this problem illustrated earlier is in fact considering if there exist $\emptyset\neq N\subset\mathbb{Z}/m\mathbb{Z}$ satisfying the following three conditions.

(I) $(N+\frac{m}{2})\cap N=\emptyset$;

(II) $(-N)\cap N=\emptyset$;

(III) for each $k\in\mathbb{Z}/m\mathbb{Z}$, $(2k-N)\cap N\neq\{k\}$.

If there does not exist such nonempty $N$ for some fixed $m$, then the polynomial system is zero-dimensional for this $m$.

In order to show that if the above mentioned $N$ does not exist then $V=\{0\}$ for the corresponding $m$, we suppose $V$ contains a nonzero point $z=(z_0,z_1,\dots,z_{m-1})$ and let $N_1$ consist of all the indices $s$ (modulo $m$) with $z_s\neq0$. It is easy to see that $N_1$ satisfies (I), because $z_s$ and $z_{\frac{m}{2}}$ cannot be nonzero simultaneously for any $s$ since $z_sz_{\frac{m}{2}+s}=0$. Similarly, $N_1$ satisfies (II). To show (III) for $N_1$, assume on the contrary that $(2k-N_1)\cap N_1=\{k\}$ for some $k$. Then $z_k\neq0$ and so $z_{\frac{m}{2}+k}=0$. Moreover, for any $j\neq k$, $j\not\in(2k-N_1)\cap N_1$. Hence $2k-j\not\in N_1$ or $j\not\in N_1$, which is to say, $z_{2k-j}=0$ or $z_j=0$. So $z_jz_{2k-j}=0$ for any $j\neq k$, contradicting $\sum\limits_{s=0}^{m-1}z_sz_{2k-s}=0$.

Edit after two answers have been posted: Will Sawin's answer saves me from going in the previous edited way. Lev Borisov wrote $f_t$ into product of two linear factors and then suggested showing all the possible linear systems are zero-dimensional. I tried to follow Lev Borisov's way, but still see no light. (If anyone knows how to probably do it, point out for me please.) However, I figured out how to show the system is zero-dimensional for $m=10,12,14$. I will upgrade here my study progress to this problem.

Hereafter, I will use the mod $m$ indices. The following observations will be useful.

Claim 1: Let $a\in(\mathbb{Z}/m\mathbb{Z})^\times$. If $(x_0,x_1,\dots,x_{m-1})\in V$, then $(x_0,x_a,\dots,x_{a(m-1)})$ and $(x_{m/2},x_{1+m/2},\dots,x_{m-1+m/2})$ are both in $V$.

In light of Claim 1, define maps $\phi_a$ and $\psi_a$ on $\mathbb{Z}/m\mathbb{Z}$ for each $a\in\mathbb{Z}/m\mathbb{Z})^\times$ by $$ \phi_a(x):x\mapsto ax+m(1+\rho(a))/4,\quad\psi_a(x):x\mapsto ax+m(1-\rho(a))/4, $$ where $\rho$ is the Jacobi symbol mod $m$. Then all the $\phi_a$ and $\psi_a$ form an abelian group $G$ of order $2\varphi(m)$, and all the $\phi_a$ form a subgroup $H$ of order $\varphi(m)$. Let $G$ act on $\mathbb{C}[z_0,\dots,z_{m-1}]$ by action on the indices of $z_k$'s.

Claim 2: If $(x_0,x_1,\dots,x_{m-1})\in V$ satisfies $x_2=x_4=\dots=x_{m-2}=0$, then $x_1=x_3=\dots=x_{m-1}=0$.

Claim 2 follows from the convolution formula of discrete Fourier transform on $(x_1,x_3,\dots,x_{m-1})$. Similarly we have

Claim 3: If $(x_0,x_1,\dots,x_{m-1})\in V$ satisfies $x_1=x_3=\dots=x_{m-1}=0$, then $x_2=x_4=\dots=x_{m-2}=0$.

Case $m=10$: Multiply $z_1$ on both sides of $f_1=0$ gives $z_1^3+2z_1z_4z_8=0$. Further multiply $z_3$ on both sides gives $z_1^3z_3=0$, which is equivalent to $z_1z_3=0$. Hence by Claim 1, $z_8z_4=\phi_3(z_1z_3)=0$. This leads to $z_1^3=0$, which is equivalent to $z_1=0$. Therefore, $V=\{0\}$ by Claim 1 since $G$ acts transitively on $\mathbb{Z}/10\mathbb{Z}$.

Case $m=12$: $z_1z_3f_1=0$ gives $z_1^3z_3=0$, which is equivalent to $z_1z_3=0$. This implies $z_7z_9=\psi_1(z_1z_3)=0$ by Claim 1. Hence $f_2=0$ turns out to be $z_2^2+z_8^2=0$, which in conjunction with $z_2z_8=0$ implies $z_2=z_8=0$. Therefore, $z_4=z_{10}=0$ by Claim 1, and so $V=\{0\}$ by Claim 2.

Case $m=14$: $z_1z_3f_1=0$ gives $z_1^3z_3+2z_1z_3z_4z_{12}=0$, and $z_1z_2z_3f_1=0$ gives $z_1z_2z_3=0$. The latter implies $z_4z_1z_{12}=\psi_{11}(z_1z_2z_3)=0$ by Claim 1, which leads to $z_1^3z_3=0$, i.e. $z_1z_3=0$. Hence $z_4z_{12}=\psi_{11}(z_1z_3)=0$ and $z_{11}z_5=\phi_{11}(z_1z_3)=0$. Thus $z_1f_1=0$ turns out to be $-z_1^3=2z_1z_6z_{10}$. Put $g=\phi_3$. Then $g$ generate $H$ and the above equation can be written as $-z_1^3=2z_1z_{g^3(1)}z_{g(1)}$. Now consider any $(x_0,x_1,\dots,x_{11})\in V$. By Claim 1, $-z_{g^j(1)}^3=2z_{g^j(1)}z_{g^{j+3}(1)}z_{g^{j+1}(1)}$ for $j=0,\dots,5$, and hence we know that $x_{g^{j+1}(1)}=0\Rightarrow x_{g^j(1)}=0$. Therefore, any $x_{g^j(1)}=0$ will lead to $x_1=0$, and $$ \prod\limits_{j=0}^5-z_{g^j(1)}^3=\prod\limits_{j=0}^52z_{g^j(1)}z_{g^{j+3}(1)}z_{g^{j+1}(1)}. $$ From the above we deduce that $\prod_{j=0}^5z_{g^j(1)}=0$, and so $x_{g^j(1)}=0$ for some $j$, which leads to $x_1=0$. Thus we have shown $z_1=0$, and so $V=\{0\}$ by Claim 1 since $G$ acts transitively on $\mathbb{Z}/14\mathbb{Z}$.

Viewing the above discussion, I would suggest study first the case $m=2l$ where $l$ is prime. Even, those $l\equiv1\pmod{4}$ and $l\equiv3\pmod{4}$ may differ, and we could suppose one of them at the beginning.

$\endgroup$
4
+100
$\begingroup$

I don't have a complete solution, but the following may be helpful.

Change variables by $z_i = \sum_j y_j \xi^{ij}$ where $\xi$ is $m$-th primitive root of $1$. Then the first line equations (I am using mod $m$ notation for the indices unless otherwise stated) become $$ 0=\sum_s z_s z_{2t-s} = \sum_{s,j,k} y_jy_k \xi^{sj+(2t-s)k} =\sum_{jk}y_jy_k \xi^{2tk} (m\delta_j^k) = m \sum_k y_k^2 \xi^{2tk} $$ $$=m\sum_{k=0...m/2-1} (y_k^2+y_{m/2+k}^2)\xi^{2tk}. $$ This impies $y_k^2+y_{m/2+k}^2=0$ for all $k$, so $y_k=\pm I y_{m/2+k}$, which are linear equations on $z$.

Similarly, we get linear equations on $z$ from the second and third line in the original post. The problem is now to assure that these are of rank $m$ for any choices of signs above and any choices in the second and third lines. Good luck!

$\endgroup$
  • $\begingroup$ Thank you for your comment! Your way proposed here is actually to do discrete Fourier transform to the vector $(z_0,z_1,\dots,z_{m-1})$. I've tried this transform before but followed by trying some uncertainty principle. Now I'll try exactly your way and bless myself:-) $\endgroup$ – Binzhou Xia Sep 7 '13 at 16:36
1
$\begingroup$

I think a probabilistic method shows that $N$ satisfying all three conditions does exist for $m$ sufficiently large.

Our set will contain a random subset of $1,\dots,\lfloor \frac{m}{4} \rfloor$, and then for each $k$ in the inteval, if $a\in N$, $\frac{m}{2}-a$ will also be in $N$, and if $a\not\in N$, $\frac{m}{2}+a$ and $-a$ will be in $N$. Thus $N$ will be a set of maximal size satisfying the first two conditions, and so will have the best chance of satisfying the third condition.

Fix a $k\neq 0, \frac{m}{2}$. We wish to show that, with high probability, $(2k-N) \cap N$ contains at least two elements. Consider $a \in \mathbb Z/mZ$, $a \neq 2k, 2k+\frac{m}{2}$. Then $2k- a \in N$ if and only in $a- 2k \not \in n$. If we consider the cycle $a, a-2k, a-4k, \dots, a$, then every time it switches from $N$ to $N^c$ we get an element of the intersection, except for the two special $a$. We need to find one switch other than these special $a$ and the switch from $k$ to $-k$

Suppose the length of the cycle is at least $5$. Then the number of possible ways to put elements of the cycles in and out of $N$ until there are switches at $3$ distinct locations will be around $2^{m/5}$, which is exponentially smaller than $2^{m/4}$, so it is exponentially improbable that the third condition fails for these $k$.

The remaining values of $2k$ are $ m/2$, $\pm m/3$, $\pm m/4$. The ones with even denominators can be eliminated because their cycles include both $x$ and $m/2+x$, so there must be a switch in each cycle, so with sufficiently large $m$ there are always enough switches. This leaves only $m/3$. Here we can use the fact that if $x, m/3+x, 2m/3+x$ are all in the set, then $m/2+x, 5m/6+x, m/6+x$ must not be in the set, and vice versa. This means there are only about $2^{m/6}$ ways to choose a set which fails condition $3$, so we again get an exponentially small probability of failure.

Adding up linearly many exponentailly small probabilities stil gives an exponentially small probability of failure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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