looking for a multiplicity one prime in a finite sum - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T18:09:34Z http://mathoverflow.net/feeds/question/59653 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59653/looking-for-a-multiplicity-one-prime-in-a-finite-sum looking for a multiplicity one prime in a finite sum Hugo Chapdelaine 2011-03-26T12:45:18Z 2011-09-04T12:57:57Z <p>So I'm trying to compute the Galois group of family of polynomials (indexed by their degree) using the technique of the Newton polygon. In order to apply this technique I need to find some good prime number $p$. </p> <p>So this is the motivation behind my question that might seem a little bit unmotivated:</p> <p>Let $N$ be a large integer. Then it is not too difficult to show the following statement:</p> <p><strong>Theorem</strong>: For every prime $p$ such that $N/2&lt; p&lt; 2N/3$ one has that $p$ divides the following sum $$S_N:=\sum_{k=0}^N \binom{N+k}{k}2^{N-k}(-1)^k$$</p> <p>After many numerical examples, it always happens that most of the primes in the interval $N/2 &lt; p &lt; 2N/3$ divide $S_N$ with multiplicity one. So here is my question:</p> <p>Q: How would you show that there exists at least one prime $p$ in the interval $N/2 &lt; p &lt; 2N/3$ that divides exactly $S_N$, i.e., $p|S_N$ but $p^2\nmid S_N$ ,?</p> <p>Note that the square of the product of all primes in the interval $(\frac{N}{2},\frac{2N}{3})$ is less that $\binom{2N}{N}$, so a naive counting argument does not seem to work here. </p> <p>If you think that this problem is intractable then let me know, I'll try a different strategy. </p> http://mathoverflow.net/questions/59653/looking-for-a-multiplicity-one-prime-in-a-finite-sum/59780#59780 Answer by Aaron Meyerowitz for looking for a multiplicity one prime in a finite sum Aaron Meyerowitz 2011-03-28T00:28:45Z 2011-03-28T00:35:42Z <p>No answer, just some data. Up to $n=825$ there are 41 pairs $[p,n]$ such that $S_n \equiv 0 \mod p^2$ and $\frac n2 \lt p \lt \frac{2n}{3}$. Here they are: $\small [7, 12], [11, 21], [29, 55], [41, 68], [43, 72], [47, 80], [61, 100], [73, 136], [\mathbf{89}, 138], [\mathbf{89}, 150], [79, 156], [89, 167]$ $\small [109, 183] [\mathbf{127}, 206], [\mathbf{127}, 230], [131, 231], [157, 276], [181, 301], [199, 306], [197, 364], [227, 386], [257, 445]$ $\small [\mathbf{277}, 450], [\mathbf{277}, 475] [313, 482], [251, 492], [353, 538], [307, 542], [421, 654], [439, 670], [367, 701], [431, 702]$ $\small [\mathbf{359}, 703], [\mathbf{359}, 710], [373, 731] [401, 737], [467, 737], [409, 755], [431, 757], [491, 798], [419, 822]$</p> <p>Over the same range the (naively ) expected number of repeat divisors of that type is about $43$ so the result seems almost certainly true, but perhaps for no special reason.</p> <p>It is notable that several times one gets the same $p$ twice in a row. I don't know if it is significant however.</p>