User samir siksek - MathOverflow

Answer by Samir Siksek for How often do two powers of 2 equal two powers of 10 (when summed)?

2013-04-03T01:16:03Z

There's an elementary way of solving this (and similar equations). Let's start with $$ 1+2^n=5^a(1+10^m) $$ which you want to solve in positive integers $n$, $a$, $m$. Clearly $m < n$ and $a < n$. As wccanard points out, $2$ is a primitive root modulo $5^a$ and so we obtain that $n$ is divisible by $2 \cdot 5^{a-1}$. In particular, $$ 2 \cdot 5^{a-1} \le n. $$ Now let's use the fact that $m < n$ are reduce the equation modulo $2^m$. We obtain, $$ 5^a \equiv 1 \pmod{2^m}. $$ As in your question you write this as $$ 4a + 16 \binom{a}{2}+\cdots \equiv 0 \pmod{2^m}. $$ This implies that $2^{m-2} \mid a$, and so $$ 2^{m-2} \le a. $$ The inequalities we now have show that the left-hand side of the equation is much bigger than the right-hand side as soon as the $n$ is large!

Appended by the OP: With apologies to Samir if he had something slicker in mind, I thought I'd add my own elaboration on when $(1+2^n)$ becomes bigger than $5^a(1+10^m)$.

The first displayed inequality implies $5^a \le (5/2)n$ and the second, combined with $a \lt n$, gives $2^m \le 4a < 4n.$ Clearly, $1+10^m \lt 16^m = (2^m)^4\lt (4n)^4$. This all gives

$$2^n \lt 1+2^n = 5^a(1+10^m) \lt (5/2)n(4n)^4 = 640n^5,$$

and it's easy to check that this implies $n\lt 35$.

Knowing also that $n$ must be congruent to 2 mod 4 means we can finish the problem off by checking the factorizations of $1+2^n$ for $n=2,6,10,14,18,22,26,30,$ and $34$, which is easy enough to do. A less crude estimate than $1+10^m \lt 16^m$ might shave off a few of the larger values of $n$, but it doesn't seem worth the effort.

Answer by Samir Siksek for Rational points on surfaces of general type

2013-03-07T13:32:41Z

A Theorem of Faltings states that any proper subvariety of an abelian variety has finitely many rational points provided this subvariety does not contain a translate of any non-trivial proper abelian subvariety:

G. Faltings, The general case of S. Lang’s conjecture, pages 175–182 of Barsotti Symposium in Algebraic Geometry (Abano Terme, 1991), Perspect. Math. 15, Academic Press, San Diego, CA, 1994.

Harris and Silverman use this to show that if C is curve of genus $\ge 2$ that is neither hyperelliptic nor bielliptic, then the set of rational points on $C^{(2)}$ is finite. Here $C^{(2)}$ is the symmetric square of $C$.

J. Harris and J. H. Silverman, Bielliptic curves and symmetric products, Proceedings of the American Mathematical Society 112 (1991), no. 2, 347–356.

My understanding is that if $C$ has genus $3$ (say a plane quartic) then $C^{(2)}$ is a surface of general type.

I admit however that symmetric powers of curves are really special and probably not what the OP is hoping for.

Answer by Samir Siksek for Cubic Fields Up to Isomorphism

2013-03-03T09:42:10Z

This a theorem of Hermite (true for number fields of any degree). I don't know of a reference, but I think it is good to look at the theorems of Hunter and Martinet which give you a finite search region for the minimal polynomial of a generator of a number field of given discriminant. A great reference is

Henri Cohen, {\em Advanced topics in computational number theory}, Springer GTM 193, 2000.

Binomial moments for the number of events occuring

2012-04-09T15:42:36Z

Let $A_1,A_2,\dots,A_n$ be events on a probability space. For $0 \leq k \leq n$ let \begin{equation*} S_k=\sum_{1 \le {i_1}<{i_2}<\cdots<{i_k} \leq n} P(A_{i_1} \cap \cdots \cap A_{i_k}). \end{equation*} This is the $k$-th binomial moment of the number $m_n$ of those $A$s which occur.

Question: What bounds are known for $S_k$ in terms of $S_0,S_1,\dots,S_{k-1}$?

Note: Bonferroni-type inequalities give bounds for $P(m_n \geq t)$ in terms of linear combinations of the $S_i$ (for example Galambos, "Bonferroni Inequalities", Annals of Probability, Vol. 5 (1977), 577--581). It is possible to use these to give bounds for $S_k$ in terms of $S_0,S_1,\dots,S_{k-1}$ and $P(m_m \geq t)$ and use the fact that $0 \leq P(m_n \geq t) \leq 1$ to deduce bounds on $S_k$ in terms of $S_0,S_1,\dots,S_{k-1}$. It seems to me however that a lot is wasted that way. I am wondering if there are known ways of obtaining sharper bounds.

Answer by Samir Siksek for Square Roots of Unity modulo N^2

2013-01-18T14:40:14Z

Given the square roots of $1$ modulo $N$ you can deduce the square roots of $1$ modulo $N^2$ just by using Hensel's Lemma (without factoring). Specifically let $r$ be one of the square roots of $1$ modulo $N^2$. Then $r \equiv s \pmod{N}$ where $s$ is one of the square roots of $1$ modulo $N$. Now $r=s+\lambda N$ and you want to find $\lambda$ modulo $N$. You want $$ (s+\lambda N)^2 -1 \equiv 0 \pmod{N^2} $$ which is the same as $$ \frac{s^2-1}{N} \equiv -2s \lambda \pmod{N}. $$ So the problem reduces to solving this congruence modulo $N$.

Incidentally, in complexity terms the problem of finding square roots modulo $N$ isn't easier than factoring $N$.

Answer by Samir Siksek for Curves with infinitely many integral points consecutive Fibonacci numbers

2013-01-02T12:29:49Z

You don't need any conjectures for this. If two curves have infinitely many points in common then they have a common component (this is a basic fact of the Zariski topology). As $x^2+xy-y^2-1$ and $x^2+xy-y^2+1$ are irreducible, one of them must divide $F$.

Answer by Samir Siksek for distance between powers of 2 and powers of 3

2012-12-20T11:09:32Z

What you need is the theory of lower bounds for linear forms in logarithms. A good place to start reading about this is the following article by Evertse:

www.math.leidenuniv.nl/~evertse/dio2011-linforms.pdf

In particular, Corollary 1.8 of the article (a Corollary to a famous theorem of Matveev) gives

$$ \lvert 2^a-3^b \rvert \ge \frac{\max(2^a,3^b)}{(e \max(a,b))^{C}} $$ where $C$ is a positive constant (that is easily computable--see the proof and also the statement of Theorem 1.7).

Answer by Samir Siksek for How does one know the following surface contains no other lines?

2012-01-15T20:54:01Z

A line is given by a pair of equations: \begin{equation*} a_1 x_1 +a_2 x_2+a_3 x_3 + a_4 x_4=0, \qquad
b_1 x_1 + b_2 x_2 + b_3 x_3 + b_4 x_4=0. \end{equation*} Suppose this line is on $X$. If the minor $a_3 b_4-a_4 b_3$ is non-zero, then we may rewrite the equations of the line as \begin{equation*} x_3=a x_1+ b x_2, \qquad x_4=c x_1 + e x_2. \end{equation*} Substituting into the equation of the surface $X$ we see that the expression \begin{equation*} x_1^d+x_2^d-x_2^{d-2}(ax_1 +b x_2)(c x_1 + e x_2) \end{equation*} vanishes as polynomial in x_1 and x_2. This is clearly impossible by considering the coefficient of $x_1^d$. Hence the minor $a_3 b_4-a_4 b_3=0$. So we can suppose that one of the equations of the line is of the form $a x_1 + b x_2=0$. Assume that the line does not lie on either of the planes $x_1=0$ or $x_2=0$. Thus neither of $a$ or $b$ is zero and we may rewrite this equation as $x_1=c x_2$. Substituting in the equation for $X$ we see that the line lies on the conic \begin{equation*} (1+c^d) x_2^2 - x_3 x_4=0. \end{equation*} If $1+c^d \ne 0$, then the conic is irreducible and so does not contain a line. Hence $1+c^d=0$ and so the line is on one of the planes $x_3=0$ or $x_4=0$.

Answer by Samir Siksek for The rank of a class elliptic curves

2011-05-03T22:13:17Z

Although Junkie has answered the question, I'd like to point out that in the case of parametrized families of elliptic curves (such as this) it is often easy to find an explicit subfamily with positive rank. In the present case, let us take $x=2a^2$ and see what condition on $a$ forces this to give a point on the elliptic curve. Making this substitution we obtain. $$ y^2=6 a^4 (3 a^2-2a+1). $$ We can simplify by defining $b=y/6 a^2$. Thus $$ 6b^2=3 a^2-2a+1. $$ This is a conic with the point $(a,b)=(-1,1)$ and so we can parametrize all the solutions: $$ a=(-t^2 + 4t - 10/3)/(t^2 - 2), \qquad b=(t^2 - 8t/3 + 2)/(t^2 - 2) $$ where $t$ is rational. The argument gives that $$ (x,y)=(2a^2,6a^2 b)$$ is a rational point on the elliptic curve provided $a$, $b$ have the above shape. It should be possible through a slightly tedious computer algebra calculation to determine all rational numbers $t$ where the point above is torsion (using Mazur's Theorem), and for all other values of $t$ the rank is positive.

Answer by Samir Siksek for Integer Points on the Elliptic Curve $y^2=x^3+17$.

2011-01-23T18:21:18Z

There is a standard method for computing all integral points on an elliptic curve using David's bounds and lattice reduction. The method can be found in the book: Nigel Smart, "The Algorithmic Resolution of Diophantine Equations", Cambridge University Press.

This method is implemented in several computer algebra packages, including magma. If you type:

E:=EllipticCurve([0,0,0,0,17]); IntegralPoints(E);

into the online magma calculator at http://magma.maths.usyd.edu.au/calc/

it will give the eight points you've found already.

Certain double covers of cubic surfaces

2010-11-07T22:35:27Z

Let $S$ be a smooth cubic surface in $\mathbb{P}^3$. I would like to understand that variety $V$ that parametrizes lines $\ell$ such that $\ell \cdot S=3P$ with $P \in S$. At any point $P \in S$, let $\Pi_P$ be the tangent plane, and let $\Gamma_P=\Pi_P \cap S$. Generically, $\Gamma_P$ is a plane cubic with a node at $P$ and therefore two tangents at $P$. Each of these satisfies $\ell \cdot S=3P$. This leads us to the fact that $V \dashrightarrow S$ is a double cover. I wanted to know if $V$ has a name, and also what can we say about it.

Positivity of a finite sum

2010-07-16T11:11:40Z

Let $i$, $k$ be integers such that $2 \leq i \leq k$. I would like to show that the sum $$ \sum_{j=1}^{i-1} \frac{(-1)^{j-1}(i-j)^k}{(i-j)! (j-1)!} $$ is positive. I have carried out extensive numerical experiments to check this for small values of $k$. In fact, much more should be true. Define polynomials $$ U(x)=(x+i-1)^k $$ and $$ V(x)=x(x+1)\cdots(x+i-1). $$ Let $Q$ and $R$ be the quotient and remainder on dividing $U$ by $V$. The above sum is the leading coefficient of $R$. It seems that all the coefficients of $Q$ and $R$ are always positive, and it would be nice to prove this, but I only need the positivity of the above sum. This question has applications for proving the irrationality of certain series.

Answer by Samir Siksek for hard diophantine equation

2010-02-21T08:32:33Z

Hi,

There is no claim in my cv or elsewhere that me and Sander have solved the equation x^3+y^5+z^7=0. All my cv claims is that we're writing a paper on it! That's not the same thing.

All the best, Samir

Comment by Samir Siksek

2013-03-03T22:12:48Z

Thanks! This paper looks interesting; I'll check it out.

Comment by Samir Siksek

2013-02-06T08:12:11Z

Obviously this doesn't work for linear $f$.

Comment by Samir Siksek

2013-01-20T11:56:52Z

Thanks---I've corrected it now.

Comment by Samir Siksek

2013-01-03T09:52:46Z

The concept you're looking for is called a $\beta$-expansion. See en.wikipedia.org/wiki/Non-integer_representation

Comment by Samir Siksek

2013-01-02T12:54:04Z

The infinite sequence of points $(F_{2^n},F_{2^n+1})$ is on many curves $F(x,y)=0$. But all these curves have infinitely many points in common with $x^2+xy-y^2+1=0$. So the polynomials $F(x,y)$ and $x^2+xy-y^2+1$ have a non-constant common factor. Thus $x^2+xy-y^2+1$ divides $F$.

Comment by Samir Siksek

2012-07-19T12:57:52Z

This isn't a research question, but here's a sketch. Let $a=f(1)$. Use induction to prove the identity for integers $x$. Deduce it for rationals, and finally use continuity to prove it for real $x$.

Comment by Samir Siksek

2011-05-16T22:05:31Z

This is an easy consequence of the fact that $x^2+y^2=z^2$ is a curve of genus $0$ and so have exactly $p$ projective solutions.

Comment by Samir Siksek

2011-03-27T08:59:21Z

Are the $a$, $b$ integers or rationals? If they're integers then $a^m+b^m=1$ is easy to solve by factoring the right-hand side (for $m$ odd). If they are rationals, simply scale and you will arrive at an equation in integers of the form $a^m+b^m=c^m$.

Comment by Samir Siksek

2011-02-05T09:29:03Z

Presumably $\hat{f} : \mathrm{Aut}(N) \rightarrow \mathrm{Aut}(N)$ sends $g$ to $f^{-1} \circ g \circ f$.

Comment by Samir Siksek

2010-11-09T17:32:52Z

Thanks Felipe, the references are very useful!

Comment by Samir Siksek

2010-07-18T10:55:28Z

Thanks Fedor, that's really clever!

Comment by Samir Siksek

2010-07-16T21:22:52Z

Thanks Robin, that's great.