---
abstract: 'Let $X$ be a finite collection of sets. We count the number of ways a disjoint union of $n-1$ subsets in $X$ is a set in $X$, and estimate this number from above by $|X|^{c(n)}$ where $$c(n)=\left(1-\frac{(n-1)\ln (n-1)}{n\ln n} \right)^{-1}.$$ This extends the recent result of Kane–Tao, corresponding to the case $n=3$ where $c(3)\approx 1.725$, to an arbitrary finite number of disjoint $n-1$ partitions.'
author:
- |
    Paata Ivanisvili[^1]\
    Department of Mathematics, Kent State University\
    1300 Lefton Esplanade, Kent OH 44242\
    pivanisv@kent.edu
date: |
    \
    Mathematics Subject Classifications: 11B30
title: '**Convolution estimates and the number of disjoint partitions**'
---

Introduction
============

Let $\{0,1\}^{m}$ be the Hamming cube of dimension $m \geq 1$. Set $1^{m}:=(1,1,\ldots, 1)$ to be the corner of $\{0,1\}^{m}$. Take a finite number of functions $f_{1}, \ldots, f_{n} : \{0,1\}^{m} \to \mathbb{R}$, and define the convolution at the corner $1^{m}$ as $$\begin{aligned}
f_{1}*f_{2}*\ldots*f_{n}(1^{m}):=\sum_{x_{j} \in \{0,1\}^{m}\, :\, x_{1}+\cdots+x_{n}=1^{m}} f_{1}(x_{1})\cdots f_{n}(x_{n}). \end{aligned}$$ Given $f :\{0,1\}^{m} \to \mathbb{R}$ define its $L^{p}$ norm ($p\geq 1$) in a standard way $$\begin{aligned}
\|f\|_{p} := \left( \sum_{x \in \{0,1\}^{m}} |f(x)|^{p}\right)^{1/p}.\end{aligned}$$ For $n\in \mathbb{N}$ we set $$\begin{aligned}
p_{n} := \frac{\ln \frac{n^{n}}{(n-1)^{n-1}}}{\ln n}.\end{aligned}$$ Our main result is the following theorem

\[taot\] For any $n,m \geq 1$, and any $f_{1}, \ldots, f_{n} :\{0,1\}^{m} \to \mathbb{R}$ we have $$\begin{aligned}
\label{maininequality}
f_{1}*f_{2}*\ldots*f_{n}(1^{m})\leq \prod_{j=1}^{n} \|f_{j}\|_{p_{n}}.\end{aligned}$$ Moreover, for each fixed $n$ exponent $p_{n}$ is the best possible in the sense that it cannot be replaced by any larger number.

As an immediate application we obtain the following corollary (see Section \[kak\] below).

\[taoc\] Let $X$ be a finite collection of sets. Then $$\begin{aligned}
\label{bolof}
\left| \left\{ (A_{1}, \ldots, A_{n-1}, A) \in \underbrace{X\times \cdots \times X}_{n}\; :\ A = \bigsqcup_{j=1}^{n-1} A_{j}  \right\} \right|\leq |X|^{\frac{n}{p_{n}}},\end{aligned}$$ where $\bigsqcup$ denotes the disjoint union, and $|X|$ denotes cardinality of the set.

The corollary extends a recent result of Kane–Tao [@KT], corresponding to the case $n=3$ where $\frac{3}{p_{3}} \approx 1.725$, to an arbitrary finite number $n \geq 3$ disjoint partitions.

The proof of the theorem
========================

Following [@KT] the proof goes by induction on the dimension of the cube $\{0,1\}^{m}$. The case $m=1$, which is the most difficult, is the main contribution of the current paper.

Basis: $m=1$
------------

In this case, set $f_{j}(0)=u_{j}$ and $f_{j}(1)=v_{j}$ for $j=1,\ldots, n$. Then the inequality (\[maininequality\]) takes the form $$\begin{aligned}
\label{i1}
\sum_{j=1}^{n} u_{j} \prod_{\substack{i=1 \\ i\neq j }}^{n}v_{i} \leq \prod_{j=1}^{n} \left(|u_{j}|^{p_{n}}+|v_{j}|^{p_{n}} \right)^{1/p_{n}}.\end{aligned}$$

We do encourage the reader first to try to prove (\[i1\]) in the case $n=3$, or visit [@KT], to see what is the obstacle. For example, when $n=3$ equality in (\[i1\]) is attained at several points. Besides, direct differentiation of (\[i1\]) reveals many “bad” critical points at which finding the values of (\[i1\]) would require numerical computations [@KT]. The number of critical points together with equality cases increases as $n$ becomes larger, therefore one is forced to come up with a different idea. We will overcome this obstacle by looking at (\[i1\]) in dual coordinates.

Without loss of generality we can assume that $u_{j}$ and $v_{j}$ are nonnegative for $j=1,\ldots, n$. Moreover, we can assume that $v_{j}\neq 0$ for all $j$ otherwise the inequality (\[i1\]) is trivial. Let us divide (\[i1\]) by $\prod_{j=1}^{n} v_{j}$. Denoting $x_{j}:=(u_{j}/v_{j})^{p_{n}}$ we see that it is enough to prove the following lemma.

For any $n\geq 2$ and all $x_{1}, \ldots, x_{n} \geq  0$ we have $$\begin{aligned}
\label{mine}
\left(\sum_{i=1}^{n} x^{1/p_{n}}_{i}\right)^{p_{n}}  \leq \prod_{i=1}^{n} (1+x_{i}),\end{aligned}$$ where $p_{n} = \frac{\ln \frac{n^{n}}{(n-1)^{n-1}}}{\ln n}$

For $n=2$ the lemma is trivial. By induction on $n$, monotonicity of the map $$\begin{aligned}
p \to \left(\sum_{i=1}^{n} x^{1/p}_{i}\right)^{p},\end{aligned}$$ and the fact that $p_{n}$ is decreasing, we can assume that all $x_{i}$ are strictly positive. For convenience we set $p:=p_{n}$. Introducing new variables we rewrite (\[mine\]) as follows $$\begin{aligned}
p \ln \left( \sum x_{i} \right) \leq \sum \ln (1+x_{i}^{p}).\end{aligned}$$ Concavity of the function $\ln (x)$ provides us with a simple representation of the logarithmic function $$\begin{aligned}
\ln(x) = \min_{b \in \mathbb{R}} (b+e^{-b}x-1).\end{aligned}$$ Therefore we are left to show that for all $x_{i} >0$ and all $b_{i} \in \mathbb{R}$ we have $$\begin{aligned}
B(x,b):=  \sum (b_{i}+(1+x_{i}^{p})e^{-b_{i}}-1)-p \ln \left( \sum x_{i} \right) \geq 0,\end{aligned}$$ where $x=(x_{1}, \ldots, x_{n})$ and $b = (b_{1}, \ldots, b_{n})$. Notice that given a vector $b \in \mathbb{R}^{n}$, the infimum of $B(x,b)$ in $x$ cannot be reached at infinity because of the slow growth of the logarithmic function. Therefore, we look at critical points of $B$ in $x$ $$\begin{aligned}
x^{*}_{k} = \frac{e^{\frac{b_{k}}{p-1}}}{\left(\sum_{i} e^{\frac{b_{i}}{p-1}} \right)^{\frac{1}{p}}} \quad \text{for} \quad k=1, \ldots, n. \end{aligned}$$ Notice that $\sum x^{*}_{i} = \left( \sum_{i} e^{\frac{b_{i}}{p-1}} \right)^{\frac{p-1}{p}}$. Therefore $$\begin{aligned}
B(x^{*}, b) = \sum_{k} (b_{k} + e^{-b_{k}})+1-n-(p-1)\ln \left(\sum_{k} e^{\frac{b_{k}}{p-1}} \right).\end{aligned}$$ Setting $r:=p-1>0$, and introducing new variables again we are left to show that $$\begin{aligned}
f(y):=1-n+\sum \ln y^{r}_{i} +  \sum \frac{1}{y_{i}^{r}}  -  r \ln \left(\sum y_{i} \right) \geq 0\end{aligned}$$ for all $y_{i}>0$. It is straightforward to check that $f(y) \geq 0$ on the diagonal, i.e., when $y_{1}=y_{2}=\ldots=y_{n}$.

In general, we notice that critical points of $f(y)$ satisfy the equation $$\begin{aligned}
\label{crit}
\frac{1}{y_{i}} - \frac{1}{y_{i}^{r+1}} = \frac{1}{y_{j}}- \frac{1}{y_{j}^{r+1}}=\frac{1}{\sum y_{k}}.\end{aligned}$$ Equation (\[crit\]) gives the identity $\sum y_{i}^{-r}=n-1$, and so at critical points (\[crit\]) we are only left to show $$\begin{aligned}
\label{lll}
\sum \ln y_{i}   -  \ln \left( \sum y_{i} \right)\geq 0. \end{aligned}$$ Since the mapping $$\begin{aligned}
s \to  \frac{1}{s} - \frac{1}{s^{r+1}}, \quad s>0,\end{aligned}$$ is increasing on $(0, (1+r)^{1/r})$ and decreasing on the remaining part of the ray, we can assume without loss of generality that $k$ numbers of $x_{i}$ equal to $u\geq (1+r)^{1/r}$, and the remaining $n-k$ numbers of $x_{i}$ equal to $v\leq (1+r)^{1/r}$. Moreover, we can assume that $0<k<n$ otherwise the statement is already proved. From (\[crit\]), we have $$\begin{aligned}
\label{eq1}
\frac{1}{u}-\frac{1}{u^{r+1}} = \frac{1}{v} - \frac{1}{v^{r+1}} = \frac{1}{k u + (n-k)v}.\end{aligned}$$ From the equality of the first and the third expressions in (\[eq1\]) it follows that $$\begin{aligned}
\label{expv}
v = \frac{u^{r+1}(1-k)+ku}{(u^{r}-1)(n-k)}.\end{aligned}$$ In order $v$ to be positive we assume that the numerator of (\[expv\]) is non negative. If we plug the expression for $v$ from (\[expv\]) into the first equality of (\[eq1\]) then after some simplifications we obtain the following equation in the variable $z:=u^{r} \geq 1+r$ $$\begin{aligned}
\label{yrb}
\frac{(z-1)^{r} (n-k)^{r+1}}{(z(1-k)+k)^{r}} = (n-1)z-k.\end{aligned}$$ It follows from (\[eq1\]) that $(ku+(n-k)v)^{r} = \left(\frac{z}{z-1}\right)^{r} z$, and so using (\[yrb\]) we obtain $$\begin{aligned}
v^{r} = \frac{z (n-k)}{(n-1)z-k}.\end{aligned}$$ Therefore at critical points (\[lll\]) simplifies as follows $$\begin{aligned}
\label{last}
(n-1) \ln z + (n-k) \ln \frac{n-k}{(n-1)z-k} - r \ln \frac{z}{z-1} \geq 0.\end{aligned}$$ Now it is pretty straightforward to show that (\[last\]) is non negative even under the assumption $z \geq 1+r$ for $r = p-1 = \frac{(n-1) \ln \frac{n}{n-1}}{\ln n}$. Indeed, notice that $z > \frac{n}{n-1}$, and the map $$\begin{aligned}
k \to (n-k)\ln \frac{n-k}{(n-1)z-k} \end{aligned}$$ is increasing on $[1,n-1]$. Therefore it is enough to check nonnegativity of (\[last\]) when $k=1$, in which case the inequality follows again using $z > \frac{n}{n-1}$, and the fact that the map $$\begin{aligned}
z \to \frac{\ln \left(1+\frac{1}{z(n-1)-1} \right)}{\ln \left(1+\frac{1}{z-1} \right)}\end{aligned}$$ is increasing for $z \geq \frac{n}{n-1}$.

Choice $x_{1}=\ldots=x_{n}=\frac{1}{n-1}$ gives equality in , and this confirms the fact that $p_{n}$ is the best possible in Theorem .

Inductive step
--------------

Inductive step is the same as in [@KT] without any modifications. This is a standard argument for obtaining estimates on the Hamming cube (see for example [@IV]). In order to make the paper self contained we decided to repeat the argument.

Suppose (\[maininequality\]) is true on the Hamming cube of dimension $m$. Without loss of generality assume $f_{j} \geq 0$, and set $g_{j} :=f_{j}^{p}$ for all $j$. Define $$\begin{aligned}
B_{n}(y_{1}, \ldots, y_{n}) := y_{1}^{1/p_{n}}\cdots y_{n}^{1/p_{n}}.\end{aligned}$$ For $x_{j} \in \{0,1\}^{m+1}$, let $x_{j} = (\bar{x}_{j}, x'_{j})$ where $\bar{x}_{j}$ is the vector consisting of the first $m$ coordinates of $x_{j}$, and number $x'_{j}$ denotes the last $m+1$ coordinate of $x_{j}$. Set $$\begin{aligned}
\tilde{g}_{j}(x'_{j}):=\sum_{\bar{x}_{j} \in \{0,1\}^{m}} g_{j}(\bar{x}_{j}, x'_{j}) \quad j=1,\ldots, n. \end{aligned}$$ We have $$\begin{aligned}
&\sum_{x_{j} \in \{0,1\}^{m+1}\; :\; x_{1}+\cdots+x_{n}=1^{m+1}.}B(g_{1}(x_{1}),\ldots, g_{n}(x_{n}))=\\
&\sum_{x'_{j}\in\{0,1\}\; :\; x'_{1}+\cdots+x'_{n}=1.}\; \sum_{\bar{x}_{j} \in \{0,1\}^{m}\; :\; \bar{x}_{1}+\cdots+\bar{x}_{n}=1^{m}.}B(g_{1}(x_{1}),\ldots, g_{n}(x_{n}))\stackrel{\mathrm{induction}}{\leq}\\
& \sum_{x'_{j}\in\{0,1\}\; :\; x'_{1}+\cdots+x'_{n}=1.} B(\tilde{g}_{1}(x'_{1}), \ldots, \tilde{g}_{n}(x'_{n}))\stackrel{\mathrm{basis}}{\leq} \\
&B\left( \sum_{x_{1} \in \{0,1\}^{m+1}} g_{1}(x_{1}), \ldots, \sum_{x_{n} \in \{0,1\}^{m+1}} g_{n}(x_{n})\right).\end{aligned}$$

The proof of Corollary \[taoc\] {#kak}
-------------------------------

Without loss of generality we may assume that all the sets $A$ in $X$ are subsets of $\{1,\ldots, m\}$ with some natural $m \geq 1$ (see [@KT]). For $j=1,\ldots, n$ define functions $$f_{j} : \{0,1\}^{m} \to \{0,1\}$$ as follows: $$\begin{aligned}
f_{1}(a_{1}, \ldots, a_{m})=\ldots=f_{n-1}(a_{1}, \ldots, a_{m})=1\end{aligned}$$ if the set $\{1\leq i \leq m\; : \; a_{i}=1\}$ lies in $X$, and $f_{j}=0$ otherwise. Finally we define $$\begin{aligned}
f_{n}(a_{1}, \ldots, a_{m})=1\end{aligned}$$ if the set $\{1\leq i \leq m\; : \; a_{i}=0\}$ lies in $X$, and $f_{n}=0$ otherwise. Notice that in this case inequality (\[maininequality\]) becomes (\[bolof\]).

Acknowledgements {#acknowledgements .unnumbered}
----------------

I would like to thank an anonymous referee, and Benjamin Jaye for helpful comments.

[10]{}

D. Kane, T. Tao, A bound on Partitioning Clusters. , Volume 24, Issue 2 (2017), Paper \#P2.31, Pages 13.

P. Ivanisvili, A. Volberg. Poincaré inequality 3/2 on the Hamming cube. [[`arXiv:1608.04021`](http://arxiv.org/abs/1608.04021)]{} (2016).

[^1]: This paper is based upon work supported by the National Science Foundation under Grant No. DMS-1440140 while the author was in residence at the Mathematical Sciences Research Institute in Berkeley, California, during the Spring 2017 semester.
