# Calculate generators of an intersection of Ideals

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

• This is a very nice problem! I will put it in some collection of "exercises" (solved humanly and experimentally...) – dan_fulea May 15 at 21:02

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.

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}$$.