User christian elsholtz - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T17:36:00Z http://mathoverflow.net/feeds/user/7673 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119105/generalizations-of-cauchy-davenport-theorem/119151#119151 Answer by Christian Elsholtz for Generalizations of Cauchy-Davenport Theorem Christian Elsholtz 2013-01-17T09:06:19Z 2013-01-17T09:51:28Z <p>Take $A_1= ...=A_k={0,1,2,...,t}\subset Z/pZ$, where $\sum |A_i|-k+1=k(t+1)-k+1=p$. Hence all classes are represented as a sum.</p> <p>2 examples: $p=101, t=k=10$, or $t=1, k=p-1$.</p> <p>But the sumset $A_1 + ...+ A_k$ will represent the class $0$ just once, namely only with all $a_i=0$. More generally, the very small and very large classes ($\leq p-1$) are represented just a few times.</p> <p>On the other hand, classes near $k t/2\approx p/2$ will be represented very often.</p> <p>In fact, the expected value of the sum is $kt/2$, and there is some small standard deviation interval around it, which will get the bulk of all combinations.</p> <p>On average, a class will have $(t+1)^k/p$ many representations, for classes near $kt/2$ this will be even higher. Therefore, in the above situation the ratio $N_{\max}/N_{\min}\geq ((t+1)^k/p)/1$ is not bounded by an absolute constant. (For example, if $t=1$, $k = p-1$).</p> <p>If you choose $k$ and $t$ larger so that $kt \approx 5p$, for example, I still expect that the sums are clustered near the expected value.</p> http://mathoverflow.net/questions/105786/erdos-straus-with-4-terms/105801#105801 Answer by Christian Elsholtz for Erdos-Straus with 4 terms Christian Elsholtz 2012-08-29T07:46:43Z 2012-08-29T07:52:20Z <p>Sums of 4 (or generally $k$) unit fractions are by no means trivial.</p> <p>There is a general criterion to Y. Rav (On the representation of rational numbers as a fixed sum of unit fractions. J. Reine Angew. Math. 222 (1966): 207-213.)</p> <p><a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN00218186X&amp;IDDOC=253620" rel="nofollow">http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN00218186X&amp;IDDOC=253620</a></p> <p>The equation $\frac{m}{n}= \frac{1}{x_1} + \cdots + \frac{1}{x_k}$<br> is certainly soluble for $m \leq k$, but for $m>k$ the same type of problems arise that one has for the Erdos-Straus equation.</p> <p>One can expect that for fixed $m$ and fixed $3 \leq k &lt; m$, there is some finite bound $N_{m,k}$ such that $n>N_{m,k}$ admits a solution. But this is an open problem.</p> <p>One can prove that for "almost all" $n \leq N$. The strongest version of "almost all", and a discussion of the parametrization of such equations is in C. Elsholtz, Sums of $k$ unit fractions, Trans. Amer. Math. Soc. 353 (2001), 3209-3227 </p> <p><a href="http://www.ams.org/journals/tran/2001-353-08/S0002-9947-01-02782-9/" rel="nofollow">http://www.ams.org/journals/tran/2001-353-08/S0002-9947-01-02782-9/</a></p> http://mathoverflow.net/questions/102720/better-error-bounds-for-partial-sums-of-reciprocals-of-primes/102724#102724 Answer by Christian Elsholtz for Better error bounds for partial sums of reciprocals of primes? Christian Elsholtz 2012-07-20T08:32:10Z 2012-07-20T08:32:10Z <p>In case you also want computationally explicit bounds look at Theorem 6.10 of:</p> <p>Pierre Dusart: Estimates of Some Functions Over Primes without R.H. <a href="http://arxiv.org/abs/1002.0442" rel="nofollow">http://arxiv.org/abs/1002.0442</a></p> <p>Probably the proof is for you more interesting than the Theorem itself. On the one hand side it shows (as Eric did) the connection with the error term of the prime number theorem. On the other hand, with the constants detailed in Theorem 5.2 you can construct explicit bounds of the type. If $x>x_k$, then $\vert \sum_{p &lt; x} \frac{1}{p}- B - \log \log x \vert &lt; \frac{\eta_k /k}{(\log x)^k} + \frac{\eta_k (1 + \frac{1}{k+1})}{ (\log x)^{k+1}}$.</p> <p>The asymptotic bounds given by the error term of the prime number theorem are of course stronger. (Explicit bounds of the type that Eric mentioned exist, but are probably not useful for computations).</p> http://mathoverflow.net/questions/82964/problem-regarding-subsets-that-sum-to-0/82979#82979 Answer by Christian Elsholtz for Problem regarding subsets that sum to 0 Christian Elsholtz 2011-12-08T16:55:13Z 2011-12-08T16:55:13Z <p>If I understand the question correctly, the following might give asymptotic answers of exponential size..</p> <p>1) Subsums of a Finite Sum and Extremal Sets of Vertices of the Hypercube, by Dezső Miklós, Horizons of Combinatorics, Bolyai Society Mathematical studies Vol 17, 2008.</p> <p>available on Springer link. A link to some slides: <a href="http://dimacs.rutgers.edu/Workshops/CombChallenge/slides/miklos.pdf" rel="nofollow">http://dimacs.rutgers.edu/Workshops/CombChallenge/slides/miklos.pdf</a></p> <p>2) Other work on the Littlewood-Offord problem could be relevant as well.</p> http://mathoverflow.net/questions/78394/is-this-ramsey-type-problem-an-open-problem/78427#78427 Answer by Christian Elsholtz for Is this Ramsey-type problem an open problem? Christian Elsholtz 2011-10-18T06:23:27Z 2011-10-18T06:23:27Z <p>The problem (and several extensions) was mentioned by Hindman.</p> <p>The case of two colours was solved by Graham:<br> The interval $[1,252]$ contains $x$ and $y$ such that $x,y, x+y$ and $xy$ are all monochromatic, and 252 is minimal.</p> <p>References:</p> <p>1) J Fox, Yeu-Whai Kathy Lin, and M Thibaul<br> The Clique Number of the Graph of Pairwise Sums and Products is 3 or 4</p> <p><a href="http://math.mit.edu/classes/18.821/documents/sample.pdf" rel="nofollow">http://math.mit.edu/classes/18.821/documents/sample.pdf</a> </p> <p>2) N Hindman, Partitions and sums and products of integers, Trans. Amer. Math. Soc. 247 (1979), 227-245. </p> <p><a href="http://www.ams.org/journals/tran/1979-247-00/S0002-9947-1979-0517693-4/home.html" rel="nofollow">http://www.ams.org/journals/tran/1979-247-00/S0002-9947-1979-0517693-4/home.html</a></p> <p>(This contains for example Graham's proof and extensions)</p> <p>3) R.K. Guy, Unsolved problems in number theory, section E29</p> http://mathoverflow.net/questions/57747/function-or-bounds-for-the-number-of-solutions-of-sum-limits-i0k-frac1/58404#58404 Answer by Christian Elsholtz for Function or bounds for the number of solutions of $\sum\limits_{i=0}^k \frac{1}{x_k} = 1$ Christian Elsholtz 2011-03-14T10:14:08Z 2011-03-14T10:20:22Z <p>An upper bound of about $c_0^{2^k}$ follows by elementary induction, (from your comment $x_k$ is bounded by the Sylvester sequence). Here $c_0 \approx 1.264$ is $\lim u_n^{\frac{1}{2^n}}$, ($u_n$ the $n$-th term of the Sylvester sequence).</p> <p>An upper bound of $c_0^{(1+\epsilon) 2^{k-1}}$ is in a paper by C. Sándor. Sándor also gives a lower bound: for $k \geq 3$: $exp(c \frac{k^3}{\log k })$, for some positive constant $c$. His paper is: Periodica Mathematica Hungarica Volume 47, Numbers 1-2, 215-219. On the number of solutions of the Diophantine equation $\sum_{i=1}^n\frac{1}{x_i}=1$ <a href="http://www.springerlink.com/content/tn50293862257447/" rel="nofollow">http://www.springerlink.com/content/tn50293862257447/</a></p> <p>An upper bound of $c_0^{(\frac{5}{24} +\epsilon) 2^{k-1}}$ was proved by T Browning and myself in our paper "On sums of unit fractions", which is to appear in the Illinois J of Mathematics. It is online here <a href="http://www.maths.bris.ac.uk/~matdb/preprints/es.pdf" rel="nofollow">http://www.maths.bris.ac.uk/~matdb/preprints/es.pdf</a> This paper gives an essentially best possible answer for a general fraction $\frac{m}{n}$ and $k=2$, then a nontrivial upper bound for $k=3$, and as a corollary lifts these results to general $k$. The case $\frac{m}{n}=1$ then follows.</p> <p>All in all, there is a large gap between upper and lower bound for your original question.</p> http://mathoverflow.net/questions/48477/never-appeared-forthcoming-papers/48613#48613 Answer by Christian Elsholtz for Never appeared forthcoming papers Christian Elsholtz 2010-12-08T08:29:11Z 2010-12-08T08:29:11Z <p>Here is a gap in a famous series of papers.</p> <p>G.H. Hardy, and J.E Littlewood Some problems in Partitio Numerorum, VII</p> <p>Their series of papers "Partitio Numerorum" is quite influential in the development of the Hardy-Littlewood circle method.</p> <p>Some comments on the missing part are on page 253 in a paper by R.C. Vaughan, Hardy's legacy to number theory, Journal of the Australian Mathematical Society (Series A) (1998), 65: 238-266. Cambridge University Press</p> <p><a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=4937088" rel="nofollow">http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=4937088</a></p> http://mathoverflow.net/questions/47442/diophantine-equation-with-no-integer-solutions-but-with-solutions-modulo-every-i/48058#48058 Answer by Christian Elsholtz for Diophantine equation with no integer solutions, but with solutions modulo every integer Christian Elsholtz 2010-12-02T16:05:29Z 2010-12-02T16:05:29Z <p>An example even easier than Jagy and Kaplansky's<br> $x^2+y^2+z^9 = 216p^3$, for $p=1 \bmod 4$, is given in:</p> <p>Sums of two squares and one biquadrate, by R. Dietmann, and C. Elsholtz,<br> Funct. Approx. Comment. Math. Volume 38, Number 2 (2008), 233-234.</p> <p><a href="http://www.math.tugraz.at/~elsholtz/WWW/papers/papers26de08.pdf" rel="nofollow">http://www.math.tugraz.at/~elsholtz/WWW/papers/papers26de08.pdf</a></p> <p>Here we showed:<br> $x^2+y^2+z^4=p^2$ has no positive solutions, when $p=7 \bmod 8, p$prime. Once the example is known, it's trivial to prove.</p> <p>The Jagy-Kaplansky example can be generalized to odd composite exponent, instead of 9. It seems the example above was overlooked for quite a while.</p> http://mathoverflow.net/questions/40090/prof-murtys-b-sc-thesis/40115#40115 Answer by Christian Elsholtz for Prof. Murty's B. Sc. Thesis Christian Elsholtz 2010-09-27T09:37:52Z 2010-09-27T09:37:52Z <p>If you are interested in the contents: the main part of Ram Murty's B.Sc. Thesis might be in his paper</p> <p>Primes in certain arithmetic progressions, Journal of the Madras University, (1988) 161-169, which is available online at</p> <p><a href="http://www.mast.queensu.ca/~murty/euclid.dvi" rel="nofollow">http://www.mast.queensu.ca/~murty/euclid.dvi</a></p> <p>Also, another paper may perhaps be of interest (more abstract, an extension).</p> <p>Primes in Certain Arithmetic Progressions, Ram Murty and Nithum Thain. Funct. Approx. Comment. Math. Volume 35, Number 1 (2006), 249-259. </p> http://mathoverflow.net/questions/31113/zagiers-one-sentence-proof-of-fermats-theorem/32178#32178 Answer by Christian Elsholtz for Zagier's one-sentence proof of Fermat's theorem. Christian Elsholtz 2010-07-16T14:28:27Z 2010-07-16T14:28:27Z <p>As the answers above linked to an old paper of mine (in German, and a somewhat different English preprint), some readers might like to know that an updated version is to appear very soon and is now linked on my webpage:</p> <p><a href="http://www.math.tugraz.at/~elsholtz/WWW/papers/papers30nathanson-new-address3.pdf" rel="nofollow">http://www.math.tugraz.at/~elsholtz/WWW/papers/papers30nathanson-new-address3.pdf</a></p> <p>In addition to the motivation of the Heath-Brown/Zagier proof it contains for example</p> <p>a) a discussion of a lattice point proof (section 1.6)</p> <p>b) much more historical information and links to other work</p> <p>c) an alternative motivation of the Heath-Brown-Zagier proof, due to Dijkstra (section 2.3)</p> http://mathoverflow.net/questions/102720/better-error-bounds-for-partial-sums-of-reciprocals-of-primes/102723#102723 Comment by Christian Elsholtz Christian Elsholtz 2012-07-20T08:57:21Z 2012-07-20T08:57:21Z I think the exponent $2/3$ should be $3/5$ (Vinogradov and Korobov. Some &quot;caveat&quot; is necessary, but the $\varepsilon$ cares for it). http://mathoverflow.net/questions/100528/sieve-of-atkin-60-modulo Comment by Christian Elsholtz Christian Elsholtz 2012-06-24T17:11:53Z 2012-06-24T17:11:53Z Wiki's algorithm and pseudocde do not exacty match, which makes it very confusing. W's algorithm (and the Atkin-Bernstein paper) define 2,3,5 as primes, then only study the 16 reduced classes mod 60 (presieving). The first step covers the 8 of 16 cases which are 1 mod 4. On the contrary, Wiki's pseudocode defines 2 and 3 as primes, presieves mod 12. The first step covers 2 of 4 cases mod 12. W's pseudocode is not optimized for constant factors! The mod 60 approach seems more elaborate. Example: 65 is presieved by Atkin-Bernstein. whereas the pseudocode finds it composite via 65=64+1+16+49 http://mathoverflow.net/questions/58041/put-as-many-points-as-possible-in-an-equilateral-triangle-of-side-1-with-their-mi Comment by Christian Elsholtz Christian Elsholtz 2011-03-10T07:49:21Z 2011-03-10T07:49:21Z The Heilbronn triangle problem asks a similar question about areas, rather than distances. <a href="http://mathworld.wolfram.com/HeilbronnTriangleProblem.html" rel="nofollow">mathworld.wolfram.com/&hellip;</a> What is the maximum (taken over all configurations of $n$ points in the in the unit equilateral triangle) of the minimum area of all $\binom{n}{3}$ triangles. Heilbronn conjectured the order of magnitude is $\ll 1/n^2$, which was disproved. http://mathoverflow.net/questions/40819/the-difference-of-two-sums-of-unit-fractions/40827#40827 Comment by Christian Elsholtz Christian Elsholtz 2010-10-03T13:41:03Z 2010-10-03T13:41:03Z Gerry, you are right. Initially (in the first edit of my answer), I argued that the minimal nonzero (positive) difference $d(K_1,K_2,n)$ of sums of $K_1$ and $K_2$ unit fractions, with $n_i \leq n$ is bounded (below) by $\frac{1}{n^{K_1+K_2}}$, and then (unfortunately) edited this to give an incorrect stronger bound. Your question about that example: the polynomial example was found with the help of a computer search. Looking at the extremal examples and making some minor observations about he fractions involved, I've found that parametrization. http://mathoverflow.net/questions/40819/the-difference-of-two-sums-of-unit-fractions/40827#40827 Comment by Christian Elsholtz Christian Elsholtz 2010-10-02T17:31:36Z 2010-10-02T17:31:36Z $|\frac{a}{b}-\frac{c}{d}| = \frac{|ad-bc|}{bd}\geq \frac{1}{bd}$. For the last step observe that $ad-bc$ is an integer. If it's not zero, then it is at least one. So, of $b$ and $d$ are bounded above by $n^K$, you get the requested lower bound of $\frac{1}{n^{2K}}$. http://mathoverflow.net/questions/40819/the-difference-of-two-sums-of-unit-fractions/40827#40827 Comment by Christian Elsholtz Christian Elsholtz 2010-10-02T17:05:10Z 2010-10-02T17:05:10Z My argument above shows that the smallest nonzero difference $d(K,n)\geq \frac{1}{n^{2K}}$ (there was a typos, I mixed up with $\leq$. Maybe this is the lower bound you need. If $K_1 &gt;K_2$, the smallest the (nonzero) difference can be is, if both rationals (as sums of $K_1$ or $K_2$ unit fractions) have denominators of order of magnitude $n^{K_2}$ so that the nonzero difference is at least $d(K_1,K_2,n)\geq \frac{1}{n^{2K_2}}$. http://mathoverflow.net/questions/40819/the-difference-of-two-sums-of-unit-fractions/40827#40827 Comment by Christian Elsholtz Christian Elsholtz 2010-10-02T16:13:32Z 2010-10-02T16:13:32Z Indeed, that was not quite correct. (Thanks for spotting this!) If $K_1&gt;K_2$ the smallest possible order of magnitude is $\frac{1}{n^{\max(K_1,2 K_2)}}$.