Calculate generators of an intersection of Ideals

Question

$$I = (x_1^2-x_1,x_2^2-x_2,...,x_n^2-x_n,t-\sum_{i=1}^n 2^{i-1}*x_i)$$

Ideal in $\mathbb Q[x_1, ..., x_n,t]$. How can I calculate the generators of $J = I \cap \mathbb Q[t]$ by hand? I tried it with the Buchberger algorithm. I could not continue because the terms became too big and I realized that something is wrong in my approach.

Thank you so much for any help!

Rolandos

Answer 1

First of all, let us find the generator of the (principal) ideal $I_n$ (with obvious dependency on $n$) in small dimensions (for small values of $n$) by making some experiments in sage:

sage: R.<t,x1> = PolynomialRing(QQ)
sage: J = R.ideal(x1^2-x1, t-x1)

Ideal (x1^2 - x1, t - x1) of Multivariate Polynomial Ring in t, x1 over Rational Field
sage: J.elimination_ideal([x1])
Ideal (t^2 - t) of Multivariate Polynomial Ring in t, x1 over Rational Field
sage: J.elimination_ideal([x1]).gens()[0].factor()
t * (t - 1)

sage: R.<t,x1,x2> = PolynomialRing(QQ)
sage: J = R.ideal(x1^2-x1, x2^2-x2, t-x1-2*x2)
sage: J.elimination_ideal([x1, x2]).gens()[0].factor()
t * (t - 3) * (t - 2) * (t - 1)

sage: R.<t,x1,x2,x3> = PolynomialRing(QQ)
sage: J = R.ideal(x1^2-x1, x2^2-x2, x3^2-x3, t-x1-2*x2-4*x3)
sage: J.elimination_ideal([x1, x2, x3]).gens()[0].factor()
t * (t - 7) * (t - 6) * (t - 5) * (t - 4) * (t - 3) * (t - 2) * (t - 1)

sage: R.<t,x1,x2,x3,x4> = PolynomialRing(QQ)
sage: J = R.ideal(x1^2-x1, x2^2-x2, x3^2-x3, x4^2-x4, t-x1-2*x2-4*x3-8*x4)
sage: J.elimination_ideal([x1, x2, x3, x4]).gens()[0].factor()
t * (t - 15) * (t - 14) * (t - 13) * (t - 12) * (t - 11) * (t - 10) * (t - 9) * (t - 8) * (t - 7) * (t - 6) * (t - 5) * (t - 4) * (t - 3) * (t - 2) * (t - 1)

The pattern is clear, let us show this by induction. Assume that $J_n:=I_n\cap \Bbb Q[t]$ is principal and generated by the monomial polynomial $f_n$ in $t$ with roots $0,1,2,\dots 2^n-1$. Its degree is $2^n$.

We have now inductively to compute the elimination of $x_n,t_n$ from the ideal in $\Bbb Q[x_{n+1},t_n,t_{n+1}]$ generated by $$ x_{n+1}^2-x_{n+1}\ ,\ f_n(t_n)\ ,\ t_{n+1}-t_n-2^nx_{n+1}\ . $$ I will use $x=x_{n+1}$, $t=t_{n+1}$, $u=t_n$ for short, and instead the generators $$ x^2-x\ ,\ f_n(u)\ ,\ t -u-2^nx\ . $$ We first eliminate $u=t-2^nx$. So we have still to eliminate $x$ among $$ x^2-x\ ,\ f_n(t-2^nx)\ . $$ This means, we need the resultant with respect to $x$ of two $x$ polynomials. The resultant is a polynomial in $t$. This is up to a factor given by powers of the leading coefficients, a product of the difference of roots $r_1-r_2$, where $r_1$ is a running root of the first polynomial, so it is $0,1$, and $r_2$ is a running root of the second polynomial, seen as a polynomial in $x$. This leads to the result.

---

Some comments.

Considering the ideal $I_n$ as "generating equations" in the variables $x_1,x_2,\dots,x_n;t$, then we can obviously solve them first w.r.t $x_1,x_2,\dots,x_n$, each value among them can be either $0$ or $1$, each with multiplicity one, so the possible values for $t$ from the last equation are those numbers of the shape $$ x_1+2x_2+\dots+ 2^{n-1}x_n\ , $$ so $t$ is one of the values $0,1,2,\dots,2^n-1$, each taken with multiplicity one. So we expect that the elimination process leads to the polynomial with these roots.

---

At the last inductive step, to make the argument clear, we eliminate $x$ between the polynomials $$ x^2-x\ , $$ and $$ \begin{aligned} f_n(t-2^nx) &= (t-2^nx)(t-2^nx-1)(t-2^nx-2)\dots \\ &= \text{Constant} \cdot \underbrace{ \left(x-\frac {t}{2^n}\right) \left(x-\frac {t-1}{2^n}\right) \left(x-\frac {t-2}{2^n}\right) \dots \left(x-\frac {t-(2^n-1)}{2^n}\right) }_{g_n} \ . \end{aligned} $$ So we build the $x$-resolvent for $x^2-x$ and $g_n$, which is the product of all differences of roots $(r_1-r_2)$, $r_1$ being a root of $x^2-x$, and $r_2$ of $g_n$, seen as a polynomial in $x$. Or $(r_2-r_1)$ instead. (One polynomial has even degree.) We obtain the product $$ \prod_{0\le k<2^n} \left(\frac {t-k}{2^n}-0\right) \left(\frac {t-k}{2^n}-1\right) = \prod_{0\le k<2^{n+1}} \left(\frac {t-k}{2^n}\right) \ , $$ which is up to a constant $f_{n+1}$.