Daniel Kane and I have just uploaded to the arXiv our paper “A bound on partitioning clusters“, submitted to the Electronic Journal of Combinatorics. In this short and elementary paper, we consider a question that arose from biomathematical applications: given a finite family of sets (or “clusters”), how many ways can there be of partitioning a set in this family as the disjoint union of two other sets in this family? That is to say, what is the best upper bound one can place on the quantity

in terms of the cardinality of ? A trivial upper bound would be , since this is the number of possible pairs , and clearly determine . In our paper, we establish the improved bound

where is the somewhat strange exponent

so that . Furthermore, this exponent is best possible!

Actually, the latter claim is quite easy to show: one takes to be all the subsets of of cardinality either or , for a multiple of , and the claim follows readily from Stirling’s formula. So it is perhaps the former claim that is more interesting (since many combinatorial proof techniques, such as those based on inequalities such as the Cauchy-Schwarz inequality, tend to produce exponents that are rational or at least algebraic). We follow the common, though unintuitive, trick of generalising a problem to make it simpler. Firstly, one generalises the bound to the “trilinear” bound

for arbitrary finite collections of sets. One can place all the sets in inside a single finite set such as , and then by replacing every set in by its complement in , one can phrase the inequality in the equivalent form

for arbitrary collections of subsets of . We generalise further by turning sets into functions, replacing the estimate with the slightly stronger convolution estimate

for arbitrary functions on the Hamming cube , where the convolution is on the integer lattice rather than on the finite field vector space . The advantage of working in this general setting is that it becomes very easy to apply induction on the dimension ; indeed, to prove this estimate for arbitrary it suffices to do so for . This reduces matters to establishing the elementary inequality

for all , which can be done by a combination of undergraduate multivariable calculus and a little bit of numerical computation. (The left-hand side turns out to have local maxima at , with the latter being the cause of the numerology (1).)

The same sort of argument also gives an energy bound

for any subset of the Hamming cube, where

is the additive energy of . The example shows that the exponent cannot be improved.

## 17 comments

Comments feed for this article

5 February, 2017 at 8:42 pm

ravenclawprefectShould “elements of $\{1,…,n\}$” read “subsets” instead?

[Corrected, thanks – T.]5 February, 2017 at 9:45 pm

Paata IvanishviliFor functions the answer seems to be

. And it approeaches to 1 as when goes to infinity

[Hmm, I think you’re right, and the proof methods extend to this setting. We’ll add a remark to this effect in the next revision of the ms. -T.]6 February, 2017 at 3:56 am

john doea tiny comment:

In equation (1.1) S should be replaced with X

[Thanks, this will be corrected in the next revision of the ms. – T]6 February, 2017 at 1:06 pm

KodluThe notation f_1\ast f_2\ast f_3(1,\ldots,1) is clear in the paper but is somewhat opaque in the post (or at least it was opaque to me!)

8 February, 2017 at 8:26 am

VMTMinor remark: I think there is a slightly simpler proof of inequality (1.4) in the paper.

If the left-hand side achieves a maximum for , one can prove that :

imposing the vanishing of the differential, one gets that , , satisfy

and the two other equations obtained by permutation of .

Assuming wlog that , we have , . Comparison of and gives

, but since this equation can only hold if . Similarly and we deduce ,

i.e. . The case when (1.4) has a minimum on the boundary of the cube is simpler.

9 February, 2017 at 10:10 pm

Terence TaoUnfortunately the inequality is false. As discussed in the paper, there are other critical points arising from local minima rather than local maxima; in your notation, one of them is .

10 February, 2017 at 12:32 am

VMTWhoops! Sorry for wasting your time…

8 February, 2017 at 10:02 am

David SpeyerEchoing Kodlu’s complaint: I originally assumed that was convolution treating the Hamming cube as an abelian group of order . It was only after some confusion that I realized we were considering the Hamming cube as a subset of and convolving in that group. The paper’s statement is ambiguous on this point as well, although by time I looked that up I was alert to the issue.

[Clarified here and in the next revision of the ms, thanks – T.]8 February, 2017 at 11:45 am

AnonymousThis optimal exponent implies that the ratio of the best known upper bound to the best known lower bound for the above number of partitions is . Can this growth estimate of this ratio be improved ? (or even be made bounded?)

13 February, 2017 at 4:45 pm

Terence TaoProbably it can be improved. One needs to replace the right-hand side in the fourth-display by some more complicated “Bellman function” of the three sizes that grows a little bit more slowly than on the diagonal, and also gains something when the are different sizes from each other. One will probably have to do some Taylor expansion calculations near the critical point of the elementary inequality used here in order to make sure the induction closes properly.

14 February, 2017 at 5:47 pm

Paata IvanisviliBut how to close the induction? If little is in in the expression then the “Bellman function” should also depend on . I don’t quite see how these quantities propagate, or maybe I misunderstood the question.

14 February, 2017 at 6:10 pm

Terence TaoIn the paper, the gap between the upper and lower bounds is of the form , which is not quite the same thing as , though in the key examples, is of exponential size in so the gap should be something like . To make the induction close, I think one should use a Bellman function that is independent of and which is smaller than by a power of when ; it has to be carefully chosen not only in the main region where but also in the extreme cases when say one of the is much smaller than the other two (this corresponds to the fact that in addition to the main critical point of the key inequality, we also have critical points at and permutations). Finding the precise Bellman function that works may require a certain amount of trial and error and iteration (trying one Bellman function, finding out the locations where the induction fails to close, tweaking the Bellman function to repair the induction in that case, and then seeing if this causes the induction to stop working at some other location, repeating as necessary).

8 February, 2017 at 4:17 pm

Paata IvanishviliHere is the proof for the finite number of functions (not necessarily 2) which corresponds to partitions instead of $2$.

https://www.dropbox.com/s/qq4i8ihuju2iltx/Partition.pdf?dl=0

Again the question boils down to the Hamming cube of dimension 1 and the best possible power for the convolution inequality is , and for the number of partitions we obtain ( I am not sure if is the optimal power for N>3 (I just did not think about the example).

12 February, 2017 at 6:33 am

Matjaž GomilšekShouldn’t in the rhs of (1.1) be ?

[This will be corrected in the next version of the ms. -T]12 February, 2017 at 6:33 am

Matjaž GomilšekIn the preprint, that is.

14 February, 2017 at 1:46 am

SSQR (@SumantriSQR)is this has any connection with cluster algebra that initiated by fomin-zelevinski??

[No. – T.]20 February, 2017 at 5:20 pm

A Gauss-Bonnet connection - Quantum Calculus[…] are cheap, one can find them in any library or now the internet. But it is also on the internet: An example. End Side […]