Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am working a combinatorial question. I need to decide when the following function $$\frac{m(7m^2 - 22m +7)}{ \sqrt{ (m^2- 2m + 9)(9m^2 - 2m +1) } } $$takes integer values with following assumption: 1) m takes all positive integer values; 2) $(m^2- 2m + 9)(9m^2 - 2m +1)$ is a perfect square (= $n^2$ for some integer $n$). Limited computation for $m < 20000$ shows $m = 1, 5$.

Many thanks, Jianmin

share|improve this question
7  
It would be nice to know the general nature of the combinatorial problem which led to this. –  Geoff Robinson Jun 7 '11 at 18:20

3 Answers 3

up vote 15 down vote accepted

An elementary approach is enough here. If the given ratio is an integer, then any prime $p$ which divides $m^2 -2m+9$ divides either $m$ or $7m^2-22m+7$. If $p$ divides $m$ then clearly $p =3$. If $p$ divides $7m^2-22m+7$ then $p$ divides $$[7m^2-14m+63 - (7m^2-22m+7)] = 8m+56. $$ Hence either $p=2$ or $p$ divides $m+7.$ In the second case, $p$ divides $$(m^2-2m+9) -(m+7) = m^2-3m+2 = (m-1)(m-2).$$ Now $p$ divides $8$ if $m \equiv 1$ (mod p) and $p$ divides $9$ if $m \equiv 2$ (mod p). Hence $(m-1)^2 +8$ has the form $2^a 3^b$. The greatest common divisor of $7m^2 -22m+7$ and $9m^2-2m+1$ is also very restricted. If $p$ is an odd prime which divides both $7m^2-22m +7$ and $9m^2-2m+1$, then (subtracting the first from the second and dividing by $2$), $p$ divides $m^2 +10m-3$. Then (subtracting the first equation from $7$ times the new equation), $p$ divides $92m-28 = 4(23m-7)$ and hence $p$ divides $7m^2 +m = 7m^2-22m +7 + (23m-7).$ Since $p$ does not divide $m$, $p$ divides $7m+1$, and thus divides $(23m-7)-3(7m+1) = 2(m-5).$ But now $p$ also divides $7(m-5) + 36$, so $p$ divides $36$ and $p=3$.

Hence we see that $m^2 -2m+9$ has the form $2^a 3^b$ and $9m^2 - 2m+1$ has the form $2^e 3^f$ for integers $a,b,e,f$. But now notice that the greatest common divisor $d$ of $m^2 -2m+9$ and $9m^2 - 2m+1$ divides $16m-80$, which is the latter equation minus 9 times the former. Also, $16$ does not divide $d$, since` $(m-1)^2 +8$ is not divisible by 16 (and neither is $8m^2 +(m-1)^2$). If $h$ is the odd part of $d$, then $m \equiv 5$ (mod h), and $h$ divides $24$. Hence $d$ divides $24$. If $m$ is divisible by $3$, then $9m^2 - 2m+1$ must be a power of $2$, but is not divisible by $16$, yielding $m=0$ under current assumptions. Hence we may suppose that $m$ is not divisible by $3$. If $9$ divides $m^2-2m +9$, then $ m \equiv 2 $ (mod 9) so $9m^2 - 2m+1 \in \{3,12,24\}$, a contradiction. Hence $m^2-2m +9 = 24$ and $m= 5$ or $m^2-2m +9 = 8$ and $m= 1$ are the only remaining possibilities (for positive $m$ not divisible by 3, as we are currently assuming). Thus $m=1 $ and $m=5$ are the only positive integers which yield an integral value. (Later remark: Note that the additional solution $m=-1$ mentioned in the comment of Noam Elkies corresponds to the case $9m^2 - 2m+1 = 12 = m^2 -2m +9$, which does not occur for positive $m$).

share|improve this answer

The OP's specific Diophantine problem has been answered, but it's still worth pointing out a general technique that applies to problems of this kind:

Given an algebraic function $f(x)$, find all $x$ such that both $x$ and $f(x)$ are integers

whenever $f$ is not itself a polynomial but can be expanded in a power series about $x=\infty$ with rational coefficients. Such is the case for the function $$ f(m) = \frac{m (7m^2-22m+7)}{\sqrt{(m^2-2m+9)(9m^2-2m+1)}} = \frac{7}{3} m - \frac{128}{27} + O(1/m) $$ of the combinatorics problem, or indeed its denominator $$\sqrt{(m^2-2m+9)(9m^2-2m+1)} = 3m^2−\frac{10}{3}m+\frac{337}{27}+O(1/m)$$ (as I noted in my comment to C.Matthew's answer). Often $f$ is a rational function, which automatically satisfies the condition as long as it is not a polynomial. The technique is simply:

Use the power-series expansion to write $f(x) = P(x) + O(1/x)$ with $P \in {\bf Q}[x]$, find a common denominator $D$ so that $DP \in {\bf Z}[x]$, and observe that once $x$ is large enough that the $O(1/x)$ error drops below $1/D$ in absolute value the only way that $Df(x)$ can be integral is for $x$ to be a root of $f(x) = P(x)$. This reduces the problem to a finite search.

The OP didn't say where exactly his question came from, but such problems arise often in the theory of combinatorial designs and strongly regular graphs. For example, in a Moore graph of girth 5 and degree $d$, every vertex has $d$ neighbors and any two distinct vertices are xeither adjacent xor have a common neighbor, in which case that neighbor is unique. Using the fact that every eigenvalue of the adjacency matrix has integral multiplicity, one shows that either $d=2$ or $d=m^2+m+1$ for some integer $m$ such that $(m^2+m+1)(m^2+m-1) / (2m+1) \in {\bf Z}$. So we write $$ 16 \frac{(m^2+m+1) (m^2+m-1)} {2m+1} = 8m^3+12m^2+2m-1 - \frac{15}{2m+1} $$ and (since $15/(2m+1)$ cannot vanish) deduce that $2m+1 \leq 15$, so $m \leq 7$. We then find that of the remaining candidates only $m=1,2,7$ work. Hence $d$ is one of 2, 3, 7, or 57. [See for instance Cameron and Van Lint's Designs, Graphs, Codes and their Links (LMS 1991, 1996) for this and many more examples. As it happens, each of $d=2,3,7$ occurs for a unique Moore graph, namely the 5-cycle, Petersen graph, and Hoffman-Singleton graph respectively, while the existence of a Moore graph of degree 57 is a famous open problem.]

Further shortcuts may be available when $D$ and/or the implicit constant in $O(1/x)$ are large enough that the concluding search, though finite, is still inconvenient or infeasible to do exhaustively. For example, in the Moore graph problem, $15/(2m+1)$ must be integral, so $2m+1$ must be a factor of $15$, and this immediately yields the solutions $m=1,2,7$, corresponding to factors $3,5,15$. The numerator $15$ could have been predicted by from the value $15/16$ taken by $(m^2+m+1) (m^2+m-1)$ at $m=-1/2$, the root of the denominator $2m+1$. More generally if $f(x)$ is a rational function $A(x)/B(x)$ with $A,B \in {\bf Z}[x]$ relatively prime, we can use the Euclidean algorithm for polynomials to find $M,N \in {\bf Z}[x]$ such that $MA-NB$ is a nonzero integer, say $R$; then if $f(x)$ is an integer then so is $$ M(x) f(x) - N(x) = \frac{M(x)A(x) - N(x)B(x)}{B(x)} = \frac{R}{B(x)} , $$ and we need only find integer solutions of $B(x) = r$ for each of the factors $r$ of $R$ and test each of these candidates. $R$ is a factor of the resultant of $A$ and $B$. This is actually not far from G.Robinson's analysis: if we square to get the rational function $m^2 (7m^2-22m+7)^2 / ((m^2-2m+9)(9m^2-2m+1))^2$, the resultant is $2^{36} 3^{12}$, explaining the factors of 2 and 3 that arose in that solution. There are still $2 \cdot 37 \cdot 13 = 962$ factors to try (allowing negative as well as positive $r$), but that's much less than the number of candidates that the generic method would require testing.

share|improve this answer
    
This seems related to Runge's theorem. –  Felipe Voloch Jun 8 '11 at 9:23
    
I don't see how Runge's theorem relates here - can you please explain? Note that the approximating polynomial must have rational coefficients; this technique won't let you solve $y^2 = 2x^4 - 1$. –  Noam D. Elkies Jun 8 '11 at 13:29
    
By the way, here's a link to a one-page paper outlining an elementary proof of the uniqueness of the Hoffman-Singleton graph: math.harvard.edu/~elkies/Misc/hsgraph.pdf With a bit more care you can use this technique also to count the graph's symmetries (there are 252000). The group turns out to be isomorphic with $P\Sigma U_3({\bf F}_5)$, but that's considerably harder; Mathworld gives the reference Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003. –  Noam D. Elkies Jun 8 '11 at 13:35
    
It's much nicer to outline a general strategy, of course, though each individual problem of this type probably leaves some room for ingenuity. –  Geoff Robinson Jun 8 '11 at 18:01

Your condition (2) shows that you are looking for integral points (m, n) on a certain curve of genus 1. These are probably already rare. There is a side condition on n which you also require. I expect you have already found the solutions, though to prove this would require more work and theory. This would perhaps depend on establishing the rank of the curve, as elliptic curve. There are experts and software solutions for that.

share|improve this answer
2  
The curve has rank 1 so you don't get the result for free -- you have to work a little. Almost certainly, for $m$ a positive integer, $(m^2- 2m + 9)(9m^2 - 2m +1)$ is only the square of an integer for $m=1,5$ [one can check this for $m<=10^7$ in well under a minute] but the natural way to prove this would be to use a computer algebra system (which are getting quite good at finding all integral points on elliptic curves...) –  Kevin Buzzard Jun 4 '11 at 8:23
9  
Since $(m^2-2m+9)(9m^2-2m+1)$ has square leading term $9m^4$ but is not identically a square, finding all integer points is elementary regardless of the arithmetic of the elliptic curve. Expanding the square root in a Taylor series about $m=\infty$ gives $3m^2-10m/3+337/27+O(1/m)$. As soon as the $O(1/m)$ falls below $1/27$ it must vanish (and here it can't vanish since $3m^2-10m/3+337/27$ clearly cannot be an integer). So we get an effective upper bound, which is surely below your $10^7$ limit. [There's a couple more solutions if you allow negative integers $m$, namely $m=0$ and $m=-1$.] –  Noam D. Elkies Jun 4 '11 at 16:16
    
Very nice Noam! –  Kevin Buzzard Jun 5 '11 at 9:50
    
Thanks. I guess I should write up the general technique -- let me see what I can do... –  Noam D. Elkies Jun 8 '11 at 2:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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