Lewko's blog

Adam Smith on mathematicians (circa 1759)

Posted in Uncategorized by Mark Lewko on January 29, 2011

I recently came across the following passage regarding the mathematical profession from Adam Smith’s  influential work The Theory of Moral Sentiments that I thought others might find interesting:




The entire text is available here.

An improved upper bound for the sum-free subset constant

Posted in math.CO, Paper, Uncategorized by Mark Lewko on August 27, 2010

I recently arXiv’ed a short note titled An Improved Upper Bound for the Sum-free Subset Constant. In this post I will briefly describe the result.

We say a set of natural numbers A is sum-free if there is no solution to the equation x+y=z with x,y,z \in A. The following is a well-known theorem of Erdős.

Theorem Let A be a finite set of natural numbers. There exists a sum-free subset S \subseteq A such that |S| \geq \frac{1}{3}|A|.

The proof of this theorem is a common example of the probabilistic method and appears in many textbooks. Alon and Kleitman have observed that Erdős’ argument essentially gives the theorem with the slightly stronger conclusion |S| \geq \frac{|A|+1}{3}. Bourgain  has improved this further, showing that the conclusion can be strengthened to |S| \geq \frac{|A| + 2}{3}. Bourgain’s estimate is sharp for small sets, and improving it for larger sets seems to be a difficult problem. There has also been interest in establishing upper bounds for the problem. It seems likely that the constant 1/3 cannot be replaced by a larger constant, however this is an open problem. In Erdős’ 1965 paper, he showed that the constant \frac{1}{3} could not be replaced by a number greater than 3/7 \approx .429 by considering the set \{2,3,4,5,6,8,10\}. In 1990, Alon and Kleitman improved this to 12/29 \approx .414. In a recent survey of open problems in combinatorics, it is reported that Malouf has shown the constant cannot be greater than 4/10 = .4.  While we have not seen Malouf’s proof, we note that this can be established by considering the set \{1,2,3,4,5,6,8,9,10,18\}. In this note we further improve on these results by showing that the optimal constant cannot be greater than 11/28 \approx .393.

Tagged with: ,

Halstead has a home!

Posted in Uncategorized by Mark Lewko on November 21, 2009


Thin sets of primes and the Goldbach property

Posted in Fourier Analysis, math.NT, Uncategorized by Mark Lewko on November 19, 2009

As is well known, Goldbach conjectured that every even positive integer (greater than 2) is the sum of two primes. While this is a difficult open problem, progress has been made from a number of different directions. Perhaps most notably, Chen has shown that every sufficiently large even positive integer is the sum of a prime and an almost prime (that is an integer that is a product of at most two primes). In another direction, Montgomery and Vaughan have shown that if {E} is the set of positive even integers that cannot be expressed as the sum of two primes then

 \displaystyle |[0,N]\cap E| \leq |N|^{1-\delta}

for some positive constant {\delta>0}. This is stronger than the observation (which was made much earlier) that almost every positive integer can be expressed as the sum of two primes. In this post we’ll be interested in sets of integers with the property that most integers can be expressed as the sum of two elements from the set. To be more precise we’ll say that a set of positive integers {S} has the Goldbach property (GP) if the sumset {S+S} consists of a positive proportion of the integers. From the preceding discussion we have that the set of primes has the GP. (This discussion is closely related to the theory of thin bases.)

A natural first question in investigating such sets would be to ask how thin such a set can be. Simply considering the number of possible distinct sums, the reader can easily verify that a set {S} (of positive integers) with the GP must satisfy

 \displaystyle \liminf_{N\rightarrow\infty} \frac{[0,N]\cap S}{\sqrt{N}} > 0.

This is to say that a set of positive integers with the GP must satisfy {[0,N]\cap S \gg \sqrt{N}} for all large {N}. Recall that the prime number theorem gives us that {|[0,N]\cap\mathcal{P}| \approx N/\ln(N)} for the set of primes {\mathcal{P}}. Thus the primes are much thicker than a set with the GP needs to be (at least from naive combinatorial considerations).

Considering this, one might ask if there is a subset of the primes with the GP but having significantly lower density in the integers. I recently (re)discovered that the answer to this question is yes. In particular we have that

 Theorem 1 There exists a subset of the primes {\mathcal{Q}} such that {\mathcal{Q}+\mathcal{Q}} has positive density in the integers and

\displaystyle \limsup_{N\rightarrow\infty} \frac{[0,N]\cap \mathcal{Q}}{\sqrt{N}} < \infty.


Tagged with: ,

The sharp large sieve inquality





Get every new post delivered to your Inbox.