User christian elsholtz - MathOverflow

Answer by Christian Elsholtz for Generalizations of Cauchy-Davenport Theorem

2013-01-17T09:06:19Z

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.

2 examples: $p=101, t=k=10$, or $t=1, k=p-1$.

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.

On the other hand, classes near $k t/2\approx p/2$ will be represented very often.

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.

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

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.

Answer by Christian Elsholtz for Erdos-Straus with 4 terms

2012-08-29T07:46:43Z

Sums of 4 (or generally $k$) unit fractions are by no means trivial.

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.)

http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN00218186X&IDDOC=253620

The equation $\frac{m}{n}= \frac{1}{x_1} + \cdots + \frac{1}{x_k}$
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.

One can expect that for fixed $m$ and fixed $3 \leq k < m$, there is some finite bound $N_{m,k}$ such that $n>N_{m,k}$ admits a solution. But this is an open problem.

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

http://www.ams.org/journals/tran/2001-353-08/S0002-9947-01-02782-9/

Answer by Christian Elsholtz for Better error bounds for partial sums of reciprocals of primes?

2012-07-20T08:32:10Z

In case you also want computationally explicit bounds look at Theorem 6.10 of:

Pierre Dusart: Estimates of Some Functions Over Primes without R.H. http://arxiv.org/abs/1002.0442

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 < x} \frac{1}{p}- B - \log \log x \vert < \frac{\eta_k /k}{(\log x)^k} + \frac{\eta_k (1 + \frac{1}{k+1})}{ (\log x)^{k+1}} $.

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).

Answer by Christian Elsholtz for Problem regarding subsets that sum to 0

2011-12-08T16:55:13Z

If I understand the question correctly, the following might give asymptotic answers of exponential size..

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.

available on Springer link. A link to some slides: http://dimacs.rutgers.edu/Workshops/CombChallenge/slides/miklos.pdf

2) Other work on the Littlewood-Offord problem could be relevant as well.

Answer by Christian Elsholtz for Is this Ramsey-type problem an open problem?

2011-10-18T06:23:27Z

The problem (and several extensions) was mentioned by Hindman.

The case of two colours was solved by Graham:
The interval $[1,252]$ contains $x$ and $y$ such that $x,y, x+y$ and $xy$ are all monochromatic, and 252 is minimal.

References:

1) J Fox, Yeu-Whai Kathy Lin, and M Thibaul
The Clique Number of the Graph of Pairwise Sums and Products is 3 or 4

http://math.mit.edu/classes/18.821/documents/sample.pdf

2) N Hindman, Partitions and sums and products of integers, Trans. Amer. Math. Soc. 247 (1979), 227-245.

http://www.ams.org/journals/tran/1979-247-00/S0002-9947-1979-0517693-4/home.html

(This contains for example Graham's proof and extensions)

3) R.K. Guy, Unsolved problems in number theory, section E29

Answer by Christian Elsholtz for Function or bounds for the number of solutions of `$\sum\limits_{i=0}^k \frac{1}{x_k} = 1$`

2011-03-14T10:14:08Z

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).

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$ http://www.springerlink.com/content/tn50293862257447/

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 http://www.maths.bris.ac.uk/~matdb/preprints/es.pdf 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.

All in all, there is a large gap between upper and lower bound for your original question.

Answer by Christian Elsholtz for Never appeared forthcoming papers

2010-12-08T08:29:11Z

Here is a gap in a famous series of papers.

G.H. Hardy, and J.E Littlewood Some problems in Partitio Numerorum, VII

Their series of papers "Partitio Numerorum" is quite influential in the development of the Hardy-Littlewood circle method.

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

http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=4937088

Answer by Christian Elsholtz for Diophantine equation with no integer solutions, but with solutions modulo every integer

2010-12-02T16:05:29Z

An example even easier than Jagy and Kaplansky's
$x^2+y^2+z^9 = 216p^3$, for $p=1 \bmod 4$, is given in:

Sums of two squares and one biquadrate, by R. Dietmann, and C. Elsholtz,
Funct. Approx. Comment. Math. Volume 38, Number 2 (2008), 233-234.

http://www.math.tugraz.at/~elsholtz/WWW/papers/papers26de08.pdf

Here we showed:
$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.

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.

Answer by Christian Elsholtz for Prof. Murty's B. Sc. Thesis

2010-09-27T09:37:52Z

If you are interested in the contents: the main part of Ram Murty's B.Sc. Thesis might be in his paper

Primes in certain arithmetic progressions, Journal of the Madras University, (1988) 161-169, which is available online at

http://www.mast.queensu.ca/~murty/euclid.dvi

Also, another paper may perhaps be of interest (more abstract, an extension).

Primes in Certain Arithmetic Progressions, Ram Murty and Nithum Thain. Funct. Approx. Comment. Math. Volume 35, Number 1 (2006), 249-259.

Answer by Christian Elsholtz for Zagier's one-sentence proof of Fermat's theorem.

2010-07-16T14:28:27Z

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:

http://www.math.tugraz.at/~elsholtz/WWW/papers/papers30nathanson-new-address3.pdf

In addition to the motivation of the Heath-Brown/Zagier proof it contains for example

a) a discussion of a lattice point proof (section 1.6)

b) much more historical information and links to other work

c) an alternative motivation of the Heath-Brown-Zagier proof, due to Dijkstra (section 2.3)

Comment by Christian Elsholtz

2012-07-20T08:57:21Z

I think the exponent $2/3$ should be $3/5$ (Vinogradov and Korobov. Some "caveat" is necessary, but the $\varepsilon$ cares for it).

Comment by Christian Elsholtz

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

Comment by Christian Elsholtz

2011-03-10T07:49:21Z

The Heilbronn triangle problem asks a similar question about areas, rather than distances. mathworld.wolfram.com/… 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.

Comment by Christian Elsholtz

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.

Comment by Christian Elsholtz

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

Comment by Christian Elsholtz

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

Comment by Christian Elsholtz

2010-10-02T16:13:32Z

Indeed, that was not quite correct. (Thanks for spotting this!) If $K_1>K_2$ the smallest possible order of magnitude is $\frac{1}{n^{\max(K_1,2 K_2)}}$.