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$
0

2 Answers 2

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$
1
  • $\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$ Commented Sep 7, 2013 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .