#  Variations on the Erdős distinct-sums problem

Simone Costa  DICATAM, Università degli Studi di Brescia, Via Branze 43, 25123
Brescia, Italy<EMAIL_ADDRESS>,  Marco Dalai  DII, Università degli
Studi di Brescia, Via Branze 38, 25123 Brescia, Italy<EMAIL_ADDRESS>and  Stefano Della Fiore  DII, Università degli Studi di Brescia, Via Branze
38, 25123 Brescia, Italy<EMAIL_ADDRESS>
###### Abstract.

Let $\\{a_{1},...,a_{n}\\}$ be a set of positive integers with
$a_{1}<\dots<a_{n}$ such that all $2^{n}$ subset sums are distinct. A famous
conjecture by Erdős states that $a_{n}>c\cdot 2^{n}$ for some constant $c$,
while the best result known to date is of the form $a_{n}>c\cdot
2^{n}/\sqrt{n}$. In this paper, inspired by an information-theoretic
interpretation, we extend the study to vector-valued elements
$a_{i}\in\mathbb{Z}^{k}$ and we weaken the condition by requiring that only
sums corresponding to subsets of size smaller than or equal to $\lambda n$ be
distinct. For this case, we derive lower and upper bounds on the smallest
possible value of $a_{n}$.

###### Key words and phrases:

Erdős distinct-sums problem, polynomial method, probabilistic method

###### 2010 Mathematics Subject Classification:

05D40, 11B13

##  1\. Introduction

For any $n\geq 1$, consider sets $\\{a_{1},...,a_{n}\\}$ of positive integers
with $a_{1}<\dots<a_{n}$ whose subset sums are all distinct. A famous
conjecture, due to Paul Erdős, is that $a_{n}\geq c\cdot 2^{n}$ for some
constant $c>0$. Using the variance method, Erdős and Moser [12] (see also [3])
were able to prove that

$a_{n}\geq 1/4\cdot n^{-1/2}\cdot 2^{n}.$

No advances have been made so far in removing the term $n^{-1/2}$ from this
lower bound, but there have been several improvements on the constant factor,
including the work of Dubroff, Fox and Xu [13], Guy [14], Elkies [11], Bae
[5], and Aliev [1]. In particular, the best currently known lower bound states
that

$a_{n}\geq(1+o(1))\sqrt{\frac{2}{\pi}}\frac{1}{\sqrt{n}}2^{n}\,.$

Two simple proofs of this result, first obtained unpublished by Elkies and
Gleason, are presented in [13]. In the other direction, the best-known
construction is due to Bohman [6], who showed that there exist arbitrarily
large such sets with $a_{n}\leq 0.22002\cdot 2^{n}$.

In this paper, we propose a generalization of the problem in two directions.
One is that the distinct-sums condition is weakened by only requiring that the
sums of up to $\lambda n$ elements of the set be distinct, a direction with
connections with the recent study independently proposed in [4]. The second is
that the integers $a_{i}$ be replaced by elements in $\mathbb{Z}^{k}$ for some
$k\geq 1$. For these cases we derive both upper and lower bounds on the
smallest possible value of the largest component among all of the $a_{i}$’s,
that is on the smallest cube which contains all the $a_{i}$ elements.

This variation on the problem is inspired by an information-theoretic
interpretation, namely in the setting of signaling over a multiple access
channel. Looking at the original problem, we can interpret the $a_{i}$
integers as pulse amplitudes that $n$ transmitters can transmit over an
additive channel to send one bit of information each, for example, to signal
to the base station that they want to start a communication session. The
requirement that all subset sums be distinct expresses the desire that the
base station be able to infer any possible subset of active users. In this
setting, a natural assumption to consider is that only a maximum fraction of
the users might actually be active at the same time, and that signals be
vector-valued rather than scalars since the channel would be used over an
interval of time sending a sequence of pulses (codewords) rather than a single
pulse.

More formally, we consider the following problem.

######  Problem 1.1.

Let $\mathcal{F}_{\lambda,n}$ be the family of all subsets of
$\\{1,\dots,n\\}$ whose size is smaller than or equal to $\lambda n$. We are
interested in the minimum $M$ such that there exists a sequence
$\Sigma=(a_{1},\dots,a_{n})$ in $\mathbb{Z}^{k}$, $a_{i}\in[0,M]^{k}\ \forall
i$, (i.e. $\Sigma$ is $M$-bounded) such that for all distinct
$A_{1},A_{2}\in\mathcal{F}_{\lambda,n}$, $S(A_{1})\neq S(A_{2})$, where

$S(A)=\sum_{i\in A}a_{i}\,.$

In the following, we will call such sequences $\mathcal{F}_{\lambda,n}$-sum
distinct.

Throughout the paper, the logarithms are in base two and we denote the open
interval with endpoints $x$ and $y$ by $(x,y)$ and the closed interval by
$[x,y]$.

The paper is organized as follows. Section $2$ is devoted to lower bounds on
the values of $M$ in Problem 1.1. We show that for $\lambda\geq 1/2$, both the
isoperimetric approach (see [13]) and the variance method can be applied to
obtain non-trivial lower bounds. Then, in Section $3$, we derive three upper
bounds using, respectively, the combinatorial nullstellensatz, the
probabilistic method, and a direct construction.

##  2\. Lower Bounds

In this section we will derive three different lower bounds on $M$. Firstly,
we provide a very elementary (but still interesting since, for $\lambda<1/2$
we have no better results) lower bound.

######  Proposition 2.1.

Let $\Sigma=(a_{1},\dots,a_{n})$ be an $\mathcal{F}_{\lambda,n}$-sum distinct
sequence in $\mathbb{Z}^{k}$ that is $M$-bounded. Then

$M\geq(1+o(1))\cdot\begin{cases}\frac{1}{\lceil\lambda n\rceil\sqrt[k]{2\pi
n\lambda(1-\lambda)}}2^{nh(\lambda)/k}&\mbox{ if }\lambda<1/2;\\\
\frac{1}{\lceil\lambda n\rceil}\cdot 2^{(n-1)/k}&\mbox{ if
}1/2\leq\lambda<1;\\\ \frac{1}{n}\cdot 2^{n/k}&\mbox{ if
}\lambda=1;\end{cases}\,$

where $h(\lambda)=-\lambda\log\lambda-(1-\lambda)\log(1-\lambda)$ is the
binary entropy function.

###### Proof.

The maximum possible sum we can get on some coordinates is at most
$\lceil\lambda n\rceil M$. Then by the pigeonhole principle, for values of
$\lambda\in(0,1/2)$, we have that

$M^{k}\geq\frac{1}{\lceil\lambda n\rceil^{k}}\sum_{i=0}^{\lceil\lambda
n\rceil}\binom{n}{i}\geq\frac{1}{\lceil\lambda n\rceil^{k}\sqrt{2\pi
n\lambda(1-\lambda)}}2^{nh(\lambda)/k}\,.$

This leads to the asymptotic bound as $n\to\infty$

$M\geq(1+o(1))\frac{1}{\lceil\lambda n\rceil\sqrt[k]{2\pi
n\lambda(1-\lambda)}}2^{nh(\lambda)/k}.$

For values of $\lambda\in[1/2,1]$ the lower bound on $M$ can be easily derived
noticing that the sum $\sum_{i=0}^{\lceil\lambda n\rceil}\binom{n}{i}$ is
greater than or equal to $2^{n-1}$ for $\lambda\in[1/2,1)$ and it is equal to
$2^{n}$ for $\lambda=1$. Therefore, we have that

(1) $M\geq(1+o(1))\cdot\begin{cases}\frac{1}{\lceil\lambda n\rceil}\cdot
2^{(n-1)/k}&\mbox{ if }1/2\leq\lambda<1;\\\ \frac{1}{n}\cdot 2^{n/k}&\mbox{ if
}\lambda=1.\end{cases}\,$

∎

Now, if $\lambda\geq 1/2$, we see that it is possible to improve on the term
$C_{n}=1/\lceil\lambda n\rceil$ in (1) using the Harper isoperimetric
inequality (see [16]) as done in [13] for $\lambda=1$. In particular, we see
that the same bound obtained for $\lambda=1$ also holds for all $\lambda>1/2$.
For $\lambda=1/2$, instead, a weakening by a factor of $2$ appears, which can
be explained in terms of the concentration of measure around the average value
of the sums.

######  Theorem 2.2.

[Harper vertex-isoperimetric inequality] Let $\mathcal{G}$ be a family of
subsets of $[1,n]$ with cardinality
$\sum_{i=0}^{k}\binom{n}{i}\leq|\mathcal{G}|\leq 2^{n-1}$ then
$|\partial\mathcal{G}|\geq\binom{n}{k+1}$ where
${\partial\mathcal{G}=\\{F\>|\>F\in\mathcal{P}([1,n]),\min_{Y\in\mathcal{G}}|F\Delta
Y|=1\\}}$ is called the border of $\mathcal{G}$.

Inspired by [13], we obtain the following theorem.

######  Theorem 2.3.

Let $\Sigma=(a_{1},\dots,a_{n})$ be an $\mathcal{F}_{\lambda,n}$-sum distinct
sequence in $\mathbb{Z}$ that is $M$-bounded. Then

$M\geq(1+o(1))\cdot\begin{cases}\frac{1}{\sqrt{2\pi n}}\cdot 2^{n}&\text{if
}\lambda=1/2;\\\ \sqrt{\frac{2}{\pi n}}\cdot 2^{n}&\text{if
}\lambda\in(1/2,1].\end{cases}$

###### Proof.

Assume that there exists an $\mathcal{F}_{\lambda,n}$-sum distinct sequence
$\Sigma=(a_{1},a_{2},\ldots,a_{n})$ and, without loss of generality, that
$a_{1}<a_{2}<\dots<a_{n}$. Let $\mathcal{G}$ be a set of vectors
$\epsilon=(\epsilon_{1},\ldots,\epsilon_{n})$ such that
$\epsilon_{i}\in\\{-1/2,1/2\\}$ and the dot product $\epsilon\cdot\Sigma<0\
\forall\epsilon\in\mathcal{G}$. Clearly $|\mathcal{G}|=2^{n-1}$ by symmetry.
Then by Theorem 2.2 we know that $|\partial\mathcal{G}|\geq\binom{n}{\lceil
n/2\rceil}$. If we take $\eta\in\partial\mathcal{G}$ then
$0<\eta\cdot\Sigma<a_{n}$. We can express
$\partial\mathcal{G}=\partial\mathcal{G}_{1}\cup\partial\mathcal{G}_{2}$ where

$\partial\mathcal{G}_{1}=\\{\eta\in\partial\mathcal{G}:\text{supp}(\eta+1/2)\leq\lfloor\lambda
n\rfloor\\}$

and

$\partial\mathcal{G}_{2}=\\{\eta\in\partial\mathcal{G}:\text{supp}(\eta+1/2)\geq\lfloor\lambda
n\rfloor+1\\}.$

If $\lambda\in(1/2,1]$, then we have that

(2) $|\partial\mathcal{G}_{1}|\geq\binom{n}{\lceil
n/2\rceil}-|\partial\mathcal{G}_{2}|.$

Because of the definition of $\partial\mathcal{G}_{2}$

$|\partial\mathcal{G}_{2}|\leq\sum_{i=\lfloor\lambda
n\rfloor+1}^{n}\binom{n}{i}\leq 2^{h(\lambda)n}.$

Since in this case $h(\lambda)<1$, from (2) we obtain

$|\partial\mathcal{G}_{1}|\geq(1+o(1))\binom{n}{\lceil n/2\rceil}.$

Again, by the pigeonhole principle there exists
$\eta_{1},\eta_{2}\in\partial\mathcal{G}_{1}$ such that

$|(\eta_{1}-\eta_{2})\cdot\Sigma|<a_{n}/|\partial\mathcal{G}_{1}|\leq(1+o(1))a_{n}/\binom{n}{\lceil
n/2\rceil}.$

Finally, by the hypothesis of sum-distinctness we have that
$|(\eta_{1}-\eta_{2})\cdot\Sigma|\geq 1$, and hence

$a_{n}>(1+o(1))\binom{n}{\lceil n/2\rceil}=(1+o(1))\sqrt{\frac{2}{\pi n}}\cdot
2^{n}.$

For $\lambda=1/2$ we need a tweak. In this case we see that either
$\partial\mathcal{G}_{1}$ or $\partial\mathcal{G}_{2}$ is greater than or
equal to $(1/2){\binom{n}{\lceil n/2\rceil}}$. Here we note that, since
$\Sigma$ is $\mathcal{F}_{1/2,n}$-sum distinct, it is also
$\overline{\mathcal{F}_{1/2,n}}$-sum distinct, where
$\overline{\mathcal{F}_{1/2,n}}$ is the complement of $\mathcal{F}_{1/2,n}$ in
the power set $\mathcal{P}([1,n])$. Therefore we can assume, without loss of
generality, that $\partial\mathcal{G}_{1}$ is greater than or equal to
$(1/2){\binom{n}{\lceil n/2\rceil}}$. Proceeding as in the previous case, here
we obtain that

$a_{n}>(1/2)\binom{n}{\lceil n/2\rceil}=(1+o(1))\frac{1}{\sqrt{2\pi n}}\cdot
2^{n}.$

∎

######  Remark 2.4.

A simple extension of Theorem 2.3 to the case $k>1$ leads, for $\lambda>1/2$,
to the bound

$M\geq(1+o(1))\sqrt[k]{\frac{2}{\pi}}n^{\frac{1}{2k}-1}2^{n/k}.$

Although a more refined reasoning might lead to better results, we did not
manage to obtain something which could compete with Theorem 2.5 below.

Now we see that, using the variance method (see [3], [12] or [14]), it is
possible to improve the bound of Remark 2.4 whenever $k>1$ and
$\lambda\in[1/2,1]$.

######  Theorem 2.5.

Let $\lambda\geq 1/2$ and let $\Sigma=(a_{1},\dots,a_{n})$ be an
$\mathcal{F}_{\lambda,n}$-sum distinct sequence in $\mathbb{Z}^{k}$ that is
$M$-bounded. Then

$M\geq(1+o(1))\cdot\begin{cases}\sqrt{\frac{4}{\pi
n(k+2)}}\cdot\Gamma(k/2+1)^{1/k}\cdot 2^{n/k}&\text{if }\lambda=1;\\\
\sqrt{\frac{4}{\pi n(k+2)}}\cdot\Gamma(k/2+1)^{1/k}\cdot 2^{(n-1)/k}&\text{if
}1/2\leq\lambda<1;\end{cases}\,$

where $\Gamma$ is the gamma function.

###### Proof.

Let $\Sigma=(a_{1},\dots,a_{n})$ be an $M$-bounded and
$\mathcal{F}_{\lambda,n}$-sum distinct sequence in $\mathbb{Z}^{k}$ where
$\lambda\geq 1/2$. Consider a random variable
$X=\sum_{i=1}^{n}\epsilon_{i}a_{i}$ where the random vectors
$(\epsilon_{1},\epsilon_{2},\ldots,\epsilon_{n})$ are uniformly distributed
over the set
$\\{\epsilon\in\\{-1/2,1/2\\}^{n}:\text{supp}(\epsilon+1/2)\leq\lambda n\\}$.
We denote with $\mu$ and $\sigma^{2}$ respectively the expected value and the
variance of the random variable $X$.

We know that
$\sigma^{2}=\mathbb{E}[|X|^{2}]-|\mathbb{E}[X]|^{2}\leq\mathbb{E}[|X|^{2}]$.
Expanding $\mathbb{E}[|X|^{2}]$ we get

(3)
$\mathbb{E}[|X|^{2}]=1/4\sum_{i=1}^{n}|a_{i}|^{2}+2\sum_{i<j}\mathbb{E}[\epsilon_{i}\epsilon_{j}](a_{i}\cdot
a_{j}),$

where $\mathbb{E}[\epsilon_{i}\epsilon_{j}]$ does not depend on the specific
values chosen for $i$ and $j$. Then for each $i\neq j$ the following
inequality holds

$\displaystyle\mathbb{E}[\epsilon_{i}\epsilon_{j}]$
$\displaystyle=1/4\cdot\frac{\sum_{i=0}^{\lfloor\lambda
n\rfloor}\binom{n-2}{i}+\sum_{i=0}^{\lfloor\lambda
n\rfloor-2}\binom{n-2}{i}-2\sum_{i=0}^{\lfloor\lambda
n\rfloor-1}\binom{n-2}{i}}{\sum_{i=0}^{\lfloor\lambda n\rfloor}\binom{n}{i}}$
$\displaystyle=1/4\cdot\frac{\binom{n-2}{\lfloor\lambda
n\rfloor}-\binom{n-2}{\lfloor\lambda n\rfloor-1}}{\sum_{i=0}^{\lfloor\lambda
n\rfloor}\binom{n}{i}}$ (4) $\displaystyle\leq 0\,,$

where the inequality holds since $\lambda\geq 1/2$. By (3), (2), since
$|a_{i}|^{2}\leq kM^{2}$, we have that

(5) $\sigma^{2}\leq\mathbb{E}[|X|^{2}]\leq\frac{knM^{2}}{4}\,.$

Now we want to provide a lower bound on $\sigma^{2}$. We know, by the sum-
distinctness property of $\Sigma$, that each possible value of $X$, has a
probability of happening equal to $1/|\mathcal{F}_{\lambda,n}|$. Therefore,
considered the possible outcomes
$s_{1},s_{2},\dots,s_{|\mathcal{F}_{\lambda,n}|}$ of the random variable $X$
and its mean $\mu$, the variance can be expressed as follows

$\displaystyle\sigma^{2}=\frac{1}{|\mathcal{F}_{\lambda,n}|}\sum_{i=1}^{|\mathcal{F}_{\lambda,n}|}|s_{i}-\mu|^{2}.$

Thus, we can lower bound the variance by the minimum value that the above
expression can take for distinct values of the $s_{i}$’s on a discrete grid
when we relax the constraint that $\mu$ be their average. For any fixed $\mu$,
the sum is minimized when the $s_{i}$’s are packed as close as possible around
$\mu$, that is, if $d=\max_{i}|s_{i}-\mu|$, then no point in the grid at a
distance $d^{\prime}<d$ from $\mu$ is left unused (otherwise we can move one
of the $s_{i}$’s closer to $\mu$ and make the sum smaller). Let $R$ be the
radius of a ball of volume $|\mathcal{F}_{\lambda,n}|$, that is,

(6) $R=\frac{\Gamma(k/2+1)^{1/k}}{\sqrt{\pi}}|\mathcal{F}_{\lambda,n}|^{1/k}.$

By considering unit-volume non-overlapping cubes around each point in the
grid, we deduce that $d\geq R^{\prime}=R-\sqrt{k}$, so that we have an $s_{i}$
in any discrete point at distance $d^{\prime}<R^{\prime}$ from $\mu$. So, we
have

$\displaystyle\sigma^{2}\geq\frac{1}{|\mathcal{F}_{\lambda,n}|}\sum_{|s-\mu|<R^{\prime}}|s-\mu|^{2}$

where $s$ runs over all points in the ball on a discrete grid with spacing
$1$. If we thus scale everything down by $R^{\prime}$, renaming $\tilde{s}$
and $\tilde{\mu}$ the scaled quantities, we find

$\displaystyle\sigma^{2}$ $\displaystyle\geq\frac{R^{\prime
2}}{|\mathcal{F}_{\lambda,n}|}\sum_{|\tilde{s}-\tilde{\mu}|<1}|\tilde{s}-\tilde{\mu}|^{2}$
$\displaystyle=\frac{R^{\prime
2+k}}{|\mathcal{F}_{\lambda,n}|}\sum_{|\tilde{s}-\tilde{\mu}|<1}|\tilde{s}-\tilde{\mu}|^{2}\frac{1}{R^{\prime
k}}$

where now $\tilde{s}$ runs over all points in the ball on a discrete grid with
spacing $1/R^{\prime}$. For fixed $k$, as $n\to\infty$ $R^{\prime}$ grows to
infinity with $R^{\prime}=(1+o(1))R$, and the sum in the last expression
behaves as a Riemann approximation for an integral over a unit ball. So,
asymptotically as $n\to\infty$ we have

$\sigma^{2}\geq(1+o(1))\frac{R^{2+k}}{|\mathcal{F}_{\lambda,n}|}\int_{|\tilde{x}-\tilde{\mu}|\leq
1}|\tilde{x}-\tilde{\mu}|^{2}\,d\tilde{x}\,.$

Integrating in polar coordinates, using the $(k-1)$-dimensional volume of the
$(k-1)$-dimensional sphere of radius $\rho$,
$S_{k-1}(\rho)=\frac{k\pi^{k/2}}{\Gamma(k/2+1)}\rho^{k-1}$, we obtain

$\displaystyle\sigma^{2}$
$\displaystyle\geq(1+o(1))\frac{R^{2+k}}{|\mathcal{F}_{\lambda,n}|}\int_{0}^{1}S_{k-1}(\rho)\rho^{2}d\rho$
$\displaystyle\geq(1+o(1))\frac{R^{2+k}}{|\mathcal{F}_{\lambda,n}|}\frac{k\pi^{k/2}}{\Gamma(k/2+1)(k+2)}.$

Using (6) and (5) we obtain the thesis. ∎

(a) $k=1$ (b) $k>1$

Figure 1. Representation of the sub-exponential factor $C_{n}$ of the lower
bounds for $1/2\leq\lambda\leq 1$.

##  3\. Upper Bounds

The goal of this section is to provide upper bounds on $M$. We remark that the
best known upper bound for the classical Erdős distinct-sums problem (see
Bohman [6]) is always (i.e. for any $\lambda$) an upper bound on $M$ for the
$\mathcal{F}_{\lambda,n}$ distinct-sums problem. Now we will see that this
bound can be improved in several situations.

###  3.1. One dimensional Upper Bounds

In this paragraph, we consider the one-dimensional case that is $k=1$. In this
case, we can provide an upper bound by using Alon’s combinatorial
nullstellensatz. This Theorem has been applied in several Combinatorial Number
Theory problems; we refer to [17] (see also [8]) for applications in the
similar context of Alspach’s partial sums conjecture and to [7] for background
on that problem. We report here the theorem for the reader’s convenience.

######  Theorem 3.1.

[2, Theorem 1.2] Let $\mathbb{F}$ be a field and let $f=f(x_{1},\ldots,x_{k})$
be a polynomial in $\mathbb{F}[x_{1},\ldots,x_{k}]$. Suppose the degree of $f$
is $\sum\limits_{i=1}^{k}t_{i}$, where each $t_{i}$ is a nonnegative integer,
and suppose the coefficient of $\prod\limits_{i=1}^{k}x_{i}^{t_{i}}$ in $f$ is
nonzero. Then, if $A_{1},\ldots,A_{k}$ are subsets of $\mathbb{F}$ with
$|A_{i}|>t_{i}$, there are $a_{1}\in A_{1},\ldots,a_{k}\in A_{k}$ so that
$f(a_{1},\ldots,a_{k})\neq 0$.

Before providing our upper bound, we need an enumerative lemma. The bound that
we will derive is non-trivial, i.e., it is better than the one derived from
the powers of two sequence, for $\lambda<\bar{\lambda}\approx 0.113546$, so we
assume for simplicity that $\lambda<1/3$.

We define for convenience

$f(\lambda)=H(\lambda,\lambda,1-2\lambda),$

where $H(p_{1},\ldots,p_{h})=\sum_{i=1}^{h}-p_{i}\log p_{i}$ is the Shannon
entropy of a probability vector $(p_{1},\ldots,p_{h})$.

######  Lemma 3.2.

Let $\mathcal{C}_{\bar{i}}$ be the family of the unodered pairs
$\\{A_{1},A_{2}\\}$ of subsets of $[1,n]$ such that, given an element
$\bar{i}\in[1,n]$:

  * •

$A_{1}\cap A_{2}=\emptyset$;

  * •

The element $\bar{i}$ belongs to $A_{1}\cup A_{2}$;

  * •

The cardinalities of $A_{1}$ and $A_{2}$ are smaller than or equal to $\lambda
n$.

Then, for $\lambda<1/3$, we have the following upper bound on the cardinality
of $\mathcal{C}_{\bar{i}}$

$|\mathcal{C}_{\bar{i}}|<\lambda^{3}n^{2}\cdot 2^{f(\lambda)n}\,.$

###### Proof.

Suppose, without loss of generality, that $\bar{i}\in A_{1}$. Then we can
upper bound the size of $\mathcal{C}_{\bar{i}}$ as follows

$|\mathcal{C}_{\bar{i}}|\leq\sum_{i=1}^{\lfloor\lambda
n\rfloor}\sum_{j=0}^{\lfloor\lambda n\rfloor}\binom{n-1}{i-1,j,n-i-j}$

where $i$ represents the cardinality of $A_{1}$ while $j$ that of $A_{2}$.
Using the fact that
$\binom{n-1}{i-1,j,n-i-j}\leq\lambda\cdot\binom{n}{i,j,n-i-j}$ for each
$i\in[1,\lambda n]$ and $j\in[0,\lambda n]$, we get

$|\mathcal{C}_{\bar{i}}|<\lambda^{3}n^{2}\binom{n}{\lfloor\lambda
n\rfloor,\lfloor\lambda n\rfloor,n-2\lfloor\lambda n\rfloor}\,,$

since the multinomial coefficient is maximized when all numbers are as equal
as possibile. Then, by a well-known entropy bound on the multinomial
coefficient (see [9, Lemma 2.2]) we have that

$|\mathcal{C}_{\bar{i}}|<\lambda^{3}n^{2}\cdot 2^{nH(\frac{\lfloor\lambda
n\rfloor}{n},\frac{\lfloor\lambda n\rfloor}{n},1-2\frac{\lfloor\lambda
n\rfloor}{n})}\leq\lambda^{3}n^{2}\cdot 2^{nH(\lambda,\lambda,1-2\lambda)}\,$

where the last inequality holds because, for $\lambda<1/3$, $f(\lambda)$ is an
increasing function. ∎

We are now ready to state our bound.

######  Theorem 3.3.

For any $\lambda<1/3$, there exists a sequence $\Sigma=(a_{1},\dots,a_{n})$ of
$\left(\lambda^{3}n^{2}2^{f(\lambda)n}\right)$-bounded positive integers that
is $\mathcal{F}_{\lambda,n}$-sum distinct.

###### Proof.

For any pair $(A_{1},A_{2})\in\mathcal{F}_{\lambda,n}^{2}$, we define the
linear polynomial

$l_{A_{1},A_{2}}(x_{1},\dots,x_{n}):=\sum_{i\in A_{1}}x_{i}-\sum_{j\in
A_{2}}x_{j}.$

Now, let us denote by $\mathcal{P}_{\lambda,n}$ the family of the pairs
$(A_{1},A_{2})$ of elements of $\mathcal{F}_{\lambda,n}$ such that $A_{1}\cap
A_{2}=\emptyset$ and $\min(A_{1})<\min(A_{2})$. Then we set

$q_{\mathcal{F}_{\lambda,n}}(x_{1},\dots,x_{n}):=\prod_{(A_{1},A_{2})\in\mathcal{P}_{\lambda,n}}l_{A_{1},A_{2}}(x_{1},\dots,x_{n}).$

We note that, for any pair
$(A^{\prime}_{1},A^{\prime}_{2})\in\mathcal{F}_{\lambda,n}^{2}$ such that
$A^{\prime}_{1}\not=A^{\prime}_{2}$, the linear polynomial
$l_{A^{\prime}_{1},A^{\prime}_{2}}(x_{1},\dots,x_{n})$ is equal to $\pm
l_{A_{1},A_{2}}(x_{1},\dots,x_{n})$ for some
$(A_{1},A_{2})\in\mathcal{P}_{\lambda,n}$. Therefore
$\Sigma=(a_{1},\dots,a_{n})$ is $\mathcal{F}_{\lambda,n}$-sum distinct if and
only if $q_{\mathcal{F}_{\lambda,n}}(a_{1},\dots,a_{n})\not=0$.

Since $\mathbb{Z}[x_{1},\dots,x_{n}]$ is an integral domain,
$q_{\mathcal{F}_{\lambda,n}}$ is not constantly zero. Therefore there exist
$t_{1},\dots,t_{n}$, where each $t_{i}$ is a nonnegative integer, such that
the coefficient of $\prod\limits_{i=1}^{n}x_{i}^{t_{i}}$ in
$q_{\mathcal{F}_{\lambda,n}}$ is nonzero. Since $q_{\mathcal{F}_{\lambda,n}}$
is homogeneous, we also have that its degree is $\sum\limits_{i=1}^{n}t_{i}$.
Let us consider $\bar{i}$ such that $t_{\bar{i}}=\max_{i}t_{i}$. The term
$x_{\bar{i}}^{t_{\bar{i}}}$ originates from the factor $r_{\bar{i}}$ of
$q_{\mathcal{F}_{\lambda,n}}$ defined by the product

$r_{\bar{i}}(x_{1},\dots,x_{n}):=\prod_{(A_{1},A_{2})\in\mathcal{P}_{\lambda,n}:\
\bar{i}\in A_{1}\cup A_{2}}l_{A_{1},A_{2}}(x_{1},\dots,x_{n}).$

Hence, because of Lemma 3.2, we have that $t_{\bar{i}}<\lambda^{3}n^{2}\cdot
2^{f(\lambda)n}$. This means that the hypotheses of Theorem 3.1 are satisfied
whenever $M\geq\lambda^{3}n^{2}\cdot 2^{f(\lambda)n}>\max_{i}t_{i}$ and hence,
under this constraint, there exist $a_{1}\in[1,M],\ldots,a_{n}\in[1,M]$ such
that $q_{\mathcal{F}_{\lambda,n}}(a_{1},\ldots,a_{n})\neq 0$. ∎

We recall that the result of Theorem 3.3 is non-trivial only when
$\lambda<\bar{\lambda}\approx 0.113546$. Now, we investigate the range
$\lambda\in[\bar{\lambda},1/4)$; here we provide a direct construction that
improves the constant of Bohman [6] bound.

######  Lemma 3.4.

Let us consider the sequence $\widetilde{\Sigma}_{n}=(b_{1},\dots,b_{n})$
where

$b_{i}:=\begin{cases}2^{i-1}&i=1,2\dots n-1\\\
\sum_{j=0}^{j<n/2-1}2^{2j}&i=n;\end{cases}$

Then, given two subsets $A_{1},A_{2}$ of $[1,n]$ such that
$|A_{1}|+|A_{2}|<n/2$,

$S(A_{1})=\sum_{i\in A_{1}}b_{i}\not=\sum_{j\in A_{2}}b_{j}=S(A_{2}).$

The structure of the set $\widetilde{\Sigma}_{n}$ is better understood by
writing a table of the binary representations of the integers $b_{n}$, as
shown in Figure 2.

Figure 2. Binary representation of the $b_{n}$ integers used in Lemma 3.4.

###### Proof.

Let us suppose, by contradiction, that there exist $n$, $A_{1}$ and $A_{2}$
with $|A_{1}|+|A_{2}|<n/2$ such that $S(A_{1})=S(A_{2})$, and let us consider
the smallest $n$ for which this holds.

We note that if two sets $A_{1}$ and $A_{2}$ have the same sum, then also
$A_{1}\setminus(A_{1}\cap A_{2})$ and $A_{2}\setminus(A_{1}\cap A_{2})$ have
the same sum. Therefore we may also assume that $A_{1}$ and $A_{2}$ are
disjoint. Since a simple check shows that the thesis is true for $n\leq 5$,
$n$ must be bigger than $5$. Moreover, since
$\widetilde{\Sigma}_{n}\setminus\\{b_{n}\\}$ is clearly sum-distinct, we can
assume without loss of generality that $n\in A_{1}$. Therefore we have

$b_{n}+\sum_{i\in A_{1}\setminus\\{n\\}}b_{i}=\sum_{j\in A_{2}}b_{j}.$

which can be rewritten as

(7) $\sum_{i=0}^{i<n/2-1}2^{2i}+\sum_{i\in
A_{1}\setminus\\{n\\}}2^{i-1}=\sum_{j\in A_{2}}2^{j-1}.$

Now we divide the proof in two cases, according to whether $n$ is even or $n$
is odd. The binary representations shown in Figure 2 might be useful as a
complement in some steps of the discussion.

Consider the case of even $n$. First observe that in this case equation (7)
can rewritten by replacing $n$ with $n-1$ in the upper extreme of the first
summation, that is,

(8) $\sum_{i=0}^{i<(n-1)/2-1}2^{2i}+\sum_{i\in
A_{1}\setminus\\{n\\}}2^{i-1}=\sum_{j\in A_{2}}2^{j-1}.$

We now claim that $n-1\in A_{2}$. Indeed, if $n-1$ is neither in $A_{1}$ nor
in $A_{2}$, we see that equation (8) provides a counterexample which is
already contained in $\widetilde{\Sigma}_{n-1}$. Formally, the sets
$A^{\prime}_{1}=A_{1}\setminus\\{n\\}\cup\\{n-1\\}$ and $A^{\prime}_{2}=A_{2}$
give a counterexample for $\widetilde{\Sigma}_{n-1}$ satisfying
$|A^{\prime}_{1}|+|A^{\prime}_{2}|=|A_{1}|+|A_{2}|<(n-1)/2$, because
$|A_{1}|+|A_{2}|<n/2$ with even $n$. This contradicts the minimality of $n$.
It is easy to see that $n-1\in A_{1}$ is impossible, since we would have
$S(A_{2})\leq b_{1}+\ldots+b_{n-2}<b_{n-1}$. This implies that $n-1\in A_{2}$.
As a consequence, $n-2$ must be in $A_{1}$, for otherwise we would have
$S(A_{1})\leq
b_{n}+b_{1}+b_{2}+\ldots+b_{n-3}<2(b_{1}+b_{2}+\ldots+b_{n-3})<b_{n-1}\leq
S(A_{2})$. So $A_{1}$ contains both $n$ and $n-2$, while $A_{2}$ contains
$n-1$, and we have

$\sum_{i=0}^{i<(n-1)/2-1}2^{2i}+2^{n-3}+\sum_{i\in
A_{1}\setminus\\{n,n-2\\}}2^{i-1}=2^{n-2}+\sum_{j\in
A_{2}\setminus\\{n-1\\}}2^{j-1}\,.$

Defining now $A^{\prime}_{1}=A_{1}\setminus\\{n,n-2\\}\cup\\{n-1\\}$ and
$A^{\prime}_{2}=A_{2}\setminus\\{n-1\\}\cup\\{n-2\\}$, again these two sets
give a valid counterexample in $\widetilde{\Sigma}_{n-1}$, contradicting the
minimality of $n$.

Consider now the case of odd $n$. In this case we can rewrite (7) as

$2^{n-3}+\sum_{i=0}^{i<(n-1)/2-1}2^{2i}+\sum_{i\in
A_{1}\setminus\\{n\\}}2^{i-1}=\sum_{j\in A_{2}}2^{j-1}\,.$

We notice that $A_{2}$ must contain either $n-2$ or $n-1$, but not both,
because $b_{1}+b_{2}+\ldots+b_{n-3}<b_{n}$ but at the same time
$b_{1}+b_{2}+\ldots+b_{n-3}+b_{n}<b_{n-2}+b_{n-1}$. Also note that $n-1$
cannot be in $A_{1}$, for the same reason mentioned in the case of even $n$.
So, we are left with the following cases to consider:

a) $n-2\in A_{2}$, $n-1\notin A_{1}\cup A_{2}$ and

$2^{n-3}+\sum_{i=0}^{i<(n-1)/2-1}2^{2i}+\sum_{i\in
A_{1}\setminus\\{n\\}}2^{i-1}=\sum_{j\in
A_{2}\setminus\\{n-2\\}}2^{j-1}+2^{n-3}\,,$

In this case, by defining $A^{\prime}_{2}=A_{2}\setminus\\{n-2\\}$
$A^{\prime}_{1}=A_{1}\setminus\\{n\\}\cup\\{n-1\\}$ we see that these two sets
of indices satisfy $|A^{\prime}_{1}|+|A^{\prime}_{2}|<(n-1)/2$ and give a
counterexample in $\widetilde{\Sigma}_{n-1}$, which contradicts the minimality
of $n$.

b) $n-2\in A_{1}$, $n-1\in A_{2}$ and

$2\cdot 2^{n-3}+\sum_{i=0}^{i<(n-1)/2-1}2^{2i}+\sum_{i\in
A_{1}\setminus\\{n,n-2\\}}2^{i-1}=\sum_{j\in
A_{2}\setminus\\{n-1\\}}2^{j-1}+2^{n-2}\,,$

Here we obtain a counterexample valid for $\widetilde{\Sigma}_{n-1}$ by
setting $A^{\prime}_{1}=A_{1}\setminus\\{n,n-2\\}\cup\\{n-1\\}$ and
$A^{\prime}_{2}=A_{2}\setminus\\{n-1\\}$.

c) $n-2\notin A_{1}\cup A_{2}$, $n-1\in A_{2}$ and

$2^{n-3}+\sum_{i=0}^{i<(n-1)/2-1}2^{2i}+\sum_{i\in
A_{1}\setminus\\{n\\}}2^{i-1}=\sum_{j\in
A_{2}\setminus\\{n-1\\}}2^{j-1}+2^{n-2}\,.$

In this case we note that $n-3$ must be in $A_{1}$, for otherwise
$S(A_{1})\leq b_{n}+b_{1}+\ldots+b_{n-4}<b_{n}+b_{n-3}<b_{n-1}\leq S(A_{2})$
(see Figure 2). We can then define
$A^{\prime}_{1}=A^{\prime}_{1}\setminus\\{n,n-3\\}\cup\\{n-1\\}$ and
$A^{\prime}_{2}=A_{2}\setminus\\{n-1\\}\cup\\{n-3\\}$ and again obtain a valid
counterexample in $\widetilde{\Sigma}_{n-1}$ which contradicts the minimality
of $n$. ∎

######  Remark 3.5.

We note that the condition $|A_{1}|+|A_{2}|<n/2$ in the statement of Lemma 3.4
is tight, when $n$ is even and greater than or equal to $6$, because if we
take $A_{1}=\\{b_{n}\\}$ and $A_{2}=\\{b_{2i+1}:i=0,\ldots,n/2-2\\}$ then,
clearly, $|A_{1}|+|A_{2}|=n/2$ and ${S(A_{1})=S(A_{2})}$.

The following corollary follows.

######  Corollary 3.6.

If $\lambda<1/4$, $\widetilde{\Sigma}_{n}$ is $\mathcal{F}_{\lambda,n}$-sum
distinct.

The meaning of this Corollary is that it is possible to add one more element
to the sequence of powers of two in such a way that it remains
$\mathcal{F}_{\lambda,n}$-sum distinct. With the same procedure we can also
prove the following statement:

######  Lemma 3.7.

Let us consider the sequence $\widetilde{\Sigma}_{n}=(b_{1},\dots,b_{n})$
where, as in Lemma 3.4, we have that

$b_{i}:=\begin{cases}2^{i-1}&i=1,2\dots n-1\\\
\sum_{j=0}^{j<n/2-1}2^{2j}&i=n;\end{cases}$

Then, given two subsets $A_{1},A_{2}$ of $[1,n]$ such that
$|A_{1}|+|A_{2}|<(n-1)/2$,

$S(A_{1})=\sum_{i\in A_{1}}b_{i}\not=\sum_{j\in
A_{2}}b_{j}+2^{n-1}=S(A_{2})+2^{n-1}.$

###### Proof.

We note that the set $\widetilde{\Sigma}_{n}\cup\\{2^{n-1}\\}$ is
$\widetilde{\Sigma}_{n+1}$ whenever $n$ is odd. Therefore, in this case, a
contradiction to the statements leads to a contradiction to Lemma 3.4 and we
can assume $n$ to be even.

Hence, we suppose now we have a counterexample with $n$ even. We would have
that $b_{n}=\sum_{i=0,\ i\equiv 0\pmod{2}}^{n-4}2^{i}$ and $n$ must belong to
$A_{1}$. It follows that

$\sum_{i=0,\ i\equiv 0\pmod{2}}^{n-4}2^{i}+\sum_{i\in
A_{1}\setminus\\{n\\}}b_{i}=\sum_{j\in A_{2}}b_{j}+2^{n-1}.$

Here we note that, since

$2^{n-1}=2^{n-2}+2^{n-2}>b_{n}+\sum_{i=0}^{n-3}2^{i}=b_{n}+\sum_{i=1}^{n-2}b_{i},$

$n-1$ must also belong to $A_{1}$. In this case we would have that:

$b_{n}+2^{n-2}+\sum_{i\in A_{1}\setminus\\{n,n-1\\}}b_{i}=\sum_{j\in
A_{2}}b_{j}+2^{n-1}.$

We remark that the $(n+1)$-th element of the sequence
$\widetilde{\Sigma}_{n+1}$ is $\sum_{i=0,\ i\equiv 0\pmod{2}}^{n-2}2^{i}$ that
is $b_{n}+2^{n-2}$. It follows that the set
$(\widetilde{\Sigma}_{n}\setminus\\{b_{n}\\})\cup\\{2^{n-1},b_{n}+2^{n-2}\\}$
is $\widetilde{\Sigma}_{n+1}$. Therefore, also for $n$ even, we would obtain a
contradiction to Lemma 3.4 and thus the statement is verified. ∎

The ideas of Lemmas 3.4 and 3.7 can be adapted to the following sum-distinct
sequence.

######  Theorem 3.8 ([20]).

Given $n\geq 67$, there exists a sum-distinct sequence $\overline{\Sigma_{n}}$
of integers such that $c_{1,n}<c_{2,n}<\dots<c_{n,n}$, $0,22\cdot
2^{n}<c_{n,n}<0,22096\cdot 2^{n}$ and such that, denoted by
$(\overline{c_{1}},\overline{c_{2}},\dots,\overline{c_{67}})$ the sequence for
$n=67$, we have

$c_{i,n}=\begin{cases}2^{i-1}\mbox{ if }i\leq n-67;\\\
2^{n-67}\cdot\overline{c_{i-(n-67)}}\mbox{ otherwise.}\end{cases}$

Now we show that it is possible to add one more element also to this sequence
in such a way that it remains $\mathcal{F}_{\lambda,n}$-sum distinct. We
observe that the proof of our result does not depend on the specific
$\bar{c}_{i}$ values which appear in Theorem 3.8. Indeed, it suffices to
analyze only less significant bits in the binary representation of the
$c_{i,n}$’s, which are all zeros for $i\geq n-66$.

Figure 3. Binary representation of the $a_{n}$ integers used in Proposition
3.9.

######  Proposition 3.9.

Let $\Sigma=(a_{1},\dots,a_{n})$ be the sequence of integers defined by

$a_{i}:=\begin{cases}c_{i,n-1}&i=1\ldots,n-1\\\
\sum_{j=0}^{j<(n-68)/2-1}2^{2j}&i=n\end{cases}$

Then, if $\lambda<1/4$ and $n$ is large enough, $\Sigma$ is
$\mathcal{F}_{\lambda,n}$-sum distinct.

The structure of the set $\Sigma$ in Proposition 3.9 is better understood by
writing a table of the binary representations of the integers $a_{n}$, as
shown in Figure 3.

###### Proof.

Let us suppose, by contradiction, that there exists two disjoint sets $A_{1}$
and $A_{2}$ in $\mathcal{F}_{\lambda,n}$ such that $S(A_{1})=S(A_{2})$. We
note that, if $n\not\in A_{1}\cup A_{2}$, we would have two distinct sets of
elements of $\overline{\Sigma_{n-1}}$ with the same sums which is in
contradiction with the fact that, due to Theorem 3.8,
$\overline{\Sigma_{n-1}}$ is sum-distinct. Therefore, we may assume, without
loss of generality, that $n\in A_{1}$. It follows that

$a_{n}+\sum_{i\in A_{1}\setminus\\{n\\}}a_{i}=\sum_{j\in A_{2}}a_{j}.$

Set $n^{\prime}:=n-68$. As a generalization of the method used in Lemma 3.4,
we first look at the equation modulo some appropriate power of $2$, namely
$2^{n^{\prime}-1}$ in this case, and then consider possible reminders in the
binary expressions for the sums. We set then
$A_{1}^{\prime}:=(A_{1}\setminus[n^{\prime},n])\cup\\{n^{\prime}\\}$,
$A_{2}^{\prime}:=A_{2}\setminus[n^{\prime},n]$, and we redefine
$a_{n^{\prime}}$ as $a_{n^{\prime}}:=\sum_{i=0}^{i<n^{\prime}/2-1}2^{2i}$.
Clearly, both $A_{1}^{\prime}$ and $A_{2}^{\prime}$ are not empty because
$n^{\prime}\in A_{1}^{\prime}$. Moreover, since $S(A_{1})=S(A_{2})$,
$S(A_{2}^{\prime})\leq a_{1}+a_{2}+\ldots+a_{n^{\prime}-1}<2^{n^{\prime}-1}$
and $S(A_{1}^{\prime})\leq a_{1}+a_{2}+\ldots+a_{n^{\prime}}<2^{n^{\prime}}$
we have that either $S(A_{1}^{\prime})=S(A_{2}^{\prime})$ or
$S(A_{1}^{\prime})=S(A_{2}^{\prime})+2^{n^{\prime}-1}$.

In the first case, if $n$ is large enough, we would have that

$|A_{1}^{\prime}|+|A_{2}^{\prime}|\leq|A_{1}|+|A_{2}|\leq 2\lambda
n<n^{\prime}/2.$

This would imply that $\widetilde{\Sigma}_{n^{\prime}}$ is a contradiction to
the statement of Lemma 3.4 considered for sets $A_{1}^{\prime}$,
$A_{2}^{\prime}$ and for $n^{\prime}$.

Similarly, in the second case, if $n$ is large enough, we would have that

$|A_{1}^{\prime}|+|A_{2}^{\prime}|\leq|A_{1}|+|A_{2}|\leq 2\lambda
n<(n^{\prime}-1)/2.$

Here we would have that $\widetilde{\Sigma}_{n^{\prime}}$ is a contradiction
to the statement of Lemma 3.7 considered for sets $A_{1}^{\prime}$,
$A_{2}^{\prime}$ and for $n^{\prime}$.

Since we obtain a contradiction in all cases, $\Sigma$ is
$\mathcal{F}_{\lambda,n}$-sum distinct. ∎

In case $\lambda<1/8$ we can even add two elements to the sequence
$\overline{\Sigma}$ dividing again the coefficient by $2$. At this purpose we
need another technical lemma.

######  Lemma 3.10.

Let us consider the sequence $(d_{1},\dots,d_{n})$ where $d_{i}:=2^{i-1}.$

Then, given three subsets $A_{1},A_{2},A_{3}$ of $[1,n]$ such that
$S(A_{1})+S(A_{2})=S(A_{3})$ we have that

$|A_{1}|+|A_{2}|\geq|A_{3}|.$

###### Proof.

Assume $A_{1}$, $A_{2}$ and $A_{3}$ form a counterexample with minimum
possible value of $|A_{1}|+|A_{2}|$. By the uniqueness of the binary
representation, it is clear that $Y:=A_{1}\cap A_{2}\neq\emptyset$. Also, we
note that $n\notin Y$. Then we have

$\displaystyle\sum_{i\in A_{1}}2^{i-1}+\sum_{i\in A_{2}}2^{i-1}$
$\displaystyle=\sum_{i\in A_{1}\setminus Y}2^{i-1}+\sum_{i\in A_{2}\setminus
Y}2^{i-1}+2\sum_{i\in Y}2^{i-1}$ $\displaystyle=\sum_{i\in
A^{\prime}_{1}}2^{i-1}+\sum_{i\in A_{2}^{\prime}}2^{i-1}$

where $A^{\prime}_{1}=A_{1}\cup A_{2}\setminus Y$ and $A_{2}^{\prime}=Y+1$ is
obtained by adding $1$ to each element of $Y$. But here
$|A_{1}^{\prime}|+|A_{2}^{\prime}|=|A_{1}\cup A_{2}|<|A_{1}|+|A_{2}|$,
contradicting the assumption that the chosen counterexample minimizes
$|A_{1}|+|A_{2}|$. ∎

######  Proposition 3.11.

Let $n$ be a positive integer, let us set $n^{\prime}=\lfloor(n-69)/2\rfloor$
and let $\Sigma=(a_{1},\dots,a_{n})$ be the sequence of integers defined by

$a_{i}:=\begin{cases}\sum_{j=\lceil
n^{\prime}/2\rceil-1}^{j<(n-69)/2-1}2^{2j}&\mbox{ if }i=n;\\\
\sum_{j=0}^{j<n^{\prime}/2-1}2^{2j}&\mbox{ if }i=n-1;\\\ c_{i,n-2}&\mbox{
otherwise.}\end{cases}$

Then, if $\lambda<1/8$ and $n$ is large enough, $\Sigma$ is
$\mathcal{F}_{\lambda,n}$-sum distinct.

Figure 4. Binary representation of the $a_{n}$ integers used in Proposition
3.11 when $n$ and $n^{\prime}$ are even.

The structure of the set $\Sigma$ in Proposition 3.11 is better understood by
writing a table of the binary representations of the integers $a_{n}$. In
Figure 4 we show the table only for even $n$ and $n^{\prime}$ (the other
configurations of $n$ and $n^{\prime}$ can be easily derived).

###### Proof.

Let us suppose, by contradiction, that there exists $A_{1}$ and $A_{2}$ in
$\mathcal{F}_{\lambda,n}$ such that $S(A_{1})=\sum_{i\in
A_{1}}a_{i}=\sum_{j\in A_{1}}a_{j}=S(A_{2})$. Since $\overline{\Sigma_{n-2}}$
is sum distinct, we may assume, without loss of generality, that $n-1\in
A_{1}$ or $n\in A_{1}$ and $n-1\not\in A_{1},A_{2}$. Indeed, if both $n$ and
$n-1$ do not belong to $A_{1}\cup A_{2}$ we would have two distinct sets of
elements of $\overline{\Sigma_{n-2}}$ with the same sums which is in
contradiction with Theorem 3.8.

In the first case we may assume due to Proposition 3.9 that $n\notin A_{1}$
and hence we have

$a_{n-1}+\sum_{i\in A_{1}\setminus\\{n,n-1\\}}a_{i}=\sum_{j\in A_{2}}a_{j}.$

As done in Proposition 3.9, we first look at the equation modulo some
appropriate power of $2$, namely $2^{n^{\prime}-2}$ in this case, and then
consider possible reminders in the binary expressions for the sums. We set
$A_{1}^{\prime}:=(A_{1}\setminus[n^{\prime}-1,n])\cup\\{n^{\prime}\\}$,
$A_{2}^{\prime}:=A_{2}\setminus[n^{\prime}-1,n]$ and we rename
$a_{n^{\prime}}$ by setting
$a_{n^{\prime}}:=\sum_{i=0}^{i<n^{\prime}/2-1}2^{2i}$ where we recall that
$n^{\prime}=\lfloor(n-69)/2\rfloor$. Since $S(A_{1})=S(A_{2})$,
$S(A_{2}^{\prime})\leq a_{1}+a_{2}+\ldots+a_{n^{\prime}-2}<2^{n^{\prime}-2}$
and $S(A_{1}^{\prime})\leq
a_{1}+a_{2}+\ldots+a_{n^{\prime}-2}+a_{n^{\prime}}<2^{n^{\prime}-1}$ we have
that either $S(A_{1}^{\prime})=S(A_{2}^{\prime})$ or
$S(A_{1}^{\prime})=S(A_{2}^{\prime})+2^{n^{\prime}-2}$. In the first case this
leads to contradict the statement of Lemma 3.4 considered for the sets
$A_{1}^{\prime}$, $A_{2}^{\prime}$ and for $n^{\prime}$. In the second case,
we get a contradiction to the statement of Lemma 3.4 considered for the sets
$A_{1}^{\prime}$, $A_{2}^{\prime}\cup\\{n^{\prime}-1\\}$ and for $n^{\prime}$.

Let us assume now that $n\in A_{1}$ and $n-1\not\in A_{1},A_{2}$, that is:

(9) $a_{n}+\sum_{i\in A_{1}\setminus\\{n,n-1\\}}a_{i}=\sum_{j\in A_{2}}a_{j}.$

Here we note that by setting $A_{3}:=\\{2i+1:0\leq i<n^{\prime}/2-1\\}$,
$a_{n-1}=\sum_{j\in A_{3}}a_{j}$ so that by adding $a_{n-1}$ to both sides of
equation (9) we get

(10) $a_{n}+a_{n-1}+\sum_{i\in A_{1}\setminus\\{n,n-1\\}}a_{i}=\sum_{j\in
A_{2}}a_{j}+\sum_{j\in A_{3}}a_{j}.$

Since $|A_{2}|<\frac{1}{8}n$, there exists $h\in[n^{\prime}-1,n-69]$ that is
not in $A_{2}$ and for which we have that $a_{h}>a_{n-1}$. This implies that

(11) $2^{h}>\sum_{\begin{subarray}{c}j\in A_{2}\\\
j<h\end{subarray}}a_{j}+a_{h}>\sum_{\begin{subarray}{c}j\in A_{2}\\\
j<h\end{subarray}}a_{j}+a_{n-1}=\sum_{\begin{subarray}{c}j\in A_{2}\\\
j<h\end{subarray}}a_{j}+\sum_{j\in A_{3}}a_{j}.$

Considering the binary representation of the natural numbers there exists a
set $A_{2}^{\prime\prime}$ such that

(12) $\sum_{\begin{subarray}{c}j\in A_{2},\\\
j<h\end{subarray}}a_{j}+\sum_{j\in A_{3}}a_{j}=\sum_{j\in
A_{2}^{\prime\prime}}2^{j-1}.$

Set $A_{1}^{\prime\prime}:=(A_{1}\setminus\\{n\\})\cup\\{n-1\\}$ and redefine
$a_{n-1}$ by setting $a_{n-1}=\sum_{i=0}^{i<(n-69)/2-1}2^{2i}$. Then thanks to
the upper bound of equation (11) we know that
$A_{2}^{\prime\prime}\subseteq[1,h]$ and hence $a_{j}=2^{j-1}$ for $j\in
A_{2}^{\prime\prime}$ and equation (10) can be rewritten as:

(13) $\sum_{i\in A_{1}^{\prime\prime}}a_{i}=\sum_{j\in
A_{2}^{\prime\prime}}a_{j}+\sum_{\begin{subarray}{c}j\in A_{2}\\\
j>h\end{subarray}}a_{j}.$

Set
$A_{2}^{\prime\prime\prime}:=A_{2}^{\prime\prime}\cup(A_{2}\setminus[1,h])$.
Since $A_{2}^{\prime\prime}$ and $A_{2}\setminus[1,h]$ are disjoint, equation
(13) becomes

$\sum_{i\in A_{1}^{\prime\prime}}a_{i}=\sum_{j\in
A_{2}^{\prime\prime\prime}}a_{j}.$

Now it follows from Lemma 3.10 applied to (12) that
$|A_{2}^{\prime\prime}|\leq|A_{2}\setminus[h,n]|+|A_{3}|$. Therefore we have
that

$|A_{2}^{\prime\prime\prime}|=|A_{2}^{\prime\prime}|+|A_{2}\setminus[1,h]|\leq|A_{2}|+|A_{3}|.$

Moreover, since, $|A_{2}|\leq\lambda n<\frac{1}{8}(n-1)$ for $n$ large enough
and $|A_{3}|<\frac{1}{4}(n-1)$, we obtain that
$|A_{2}^{\prime\prime\prime}|<\frac{1}{8}(n-1)+\frac{1}{4}(n-1)$. We also have
that, for $n$ large enough, $|A_{1}^{\prime\prime}|=|A_{1}|\leq\lambda
n<\frac{1}{8}(n-1)$. Here we note that
$|A_{1}^{\prime\prime}|+|A_{2}^{\prime\prime\prime}|<\frac{1}{2}(n-1)$ but
this is in contradiction with the statement of Proposition 3.9 considered for
the sets $A_{1}^{\prime\prime},A_{2}^{\prime\prime\prime}$ and for $n-1$. ∎

As a consequence, we have the following result.

######  Theorem 3.12.

Let $\lambda<1/4$, (resp. $\lambda<1/8$) then, if $n$ is large enough, there
exists a sequence $\Sigma=(a_{1},\dots,a_{n})$ of
$\left(\frac{0,22096}{2}\cdot 2^{n}\right)$-bounded integers (resp.
$\left(\frac{0,22096}{4}\cdot 2^{n}\right)$-bounded integers) that is
$\mathcal{F}_{\lambda,n}$-sum distinct.

###  3.2. Multi-Dimensional upper bounds

In this section we consider the general case $k\geq 1$. First of all, we note
that both Theorem 3.3 and Theorem 3.12 can be used to obtain an upper bound
for the $M$ of Problem 1.1 also in $\mathbb{Z}^{k}$.

######  Proposition 3.13.

Let $\bar{\Sigma}$ be an integer $M$-bounded,
$\mathcal{F}_{\lambda^{\prime},n^{\prime}}$-sum distinct sequence of length
$n^{\prime}$. Then there exists an $M$-bounded sequence $\Sigma$ in
$\mathbb{Z}^{k}$ of length $n$ that is $\mathcal{F}_{\lambda,n}$-sum distinct
where $n=kn^{\prime}$ and $\lambda=\lambda^{\prime}/k$.

###### Proof.

We set $\bar{\Sigma}_{j}$ to be the sequence in $\mathbb{Z}^{k}$ whose $j$-th
projection is $\bar{\Sigma}$ and that is zero on the other coordinates. It
suffices to consider the sequence
$\Sigma=(\bar{\Sigma}_{1},\bar{\Sigma}_{2},\dots,\bar{\Sigma}_{k})$. Clearly
$\Sigma$ is a sequence in $\mathbb{Z}^{k}$ of length $n$. It is also easy to
see that, the existence of $A_{1},A_{2}$ in $\mathcal{F}_{\lambda,n}$ such
that $S(A_{1})=S(A_{2})$ would imply the existence of
$A_{1}^{\prime},A_{2}^{\prime}$ in $\mathcal{F}_{\lambda^{\prime},n^{\prime}}$
such that $S(A_{1}^{\prime})=S(A_{2}^{\prime})$ for $\bar{\Sigma}$. But, since
$\bar{\Sigma}$ is an $\mathcal{F}_{\lambda^{\prime},n^{\prime}}$-sum distinct
sequence, it follows that $\Sigma$ is $\mathcal{F}_{\lambda,n}$-sum distinct.
∎

On the other hand, assuming $k>1$, these results can be improved for several
values of $\lambda$ using the probabilistic method (see [3]). If $k=1$,
instead, the probabilistic method fails to beat the upper bound of Theorem 3.3
(see Remark 3.16).

We first need another enumerative lemma.

######  Lemma 3.14.

Let $\mathcal{C}$ be the family of the unordered pairs $\\{A_{1},A_{2}\\}$ of
subsets of $[1,n]$ such that:

  * •

$A_{1}\cap A_{2}=\emptyset$;

  * •

The cardinalities of $A_{1}$ and $A_{2}$ are smaller than or equal to $\lambda
n$.

Then, for $\lambda<1/3$, we have the following upper bound on the cardinality
of $\mathcal{C}$

$|\mathcal{C}|<\frac{\lambda^{2}n^{2}}{2}\cdot 2^{f(\lambda)n}\,.$

###### Proof.

It can be easily derived from the proof of Lemma 3.2. ∎

######  Theorem 3.15.

Let

$C_{\lambda,n}=\sqrt[k]{\frac{\lambda^{2}n^{2}}{2\tau_{\lambda}}2^{f(\lambda)\tau_{\lambda}}}\text{
and }\tau_{\lambda}=\left\lceil\frac{1}{2^{f(\lambda)}-1}\right\rceil.$

Then there exists a sequence $\Sigma=(a_{1},\dots,a_{n})$, for $n$ large
enough, of $\left(C_{\lambda,n}\cdot 2^{f(\lambda)n/k}\right)$-bounded
elements of $\mathbb{Z}^{k}$ that is $\mathcal{F}_{\lambda,n}$-sum distinct.

###### Proof.

We recall that, if two sets $A_{1}$ and $A_{2}$ have the same sum, then also
$A_{1}\setminus(A_{1}\cap A_{2})$ and $A_{2}\setminus(A_{1}\cap A_{2})$ have
the same sum. Therefore, a sequence $\Sigma$ is $\mathcal{F}_{\lambda,n}$-sum
distinct whenever $S(A_{1})\not=S(A_{2})$ for any
$A_{1},A_{2}\in\mathcal{F}_{\lambda,n}$ such that $A_{1}\cap A_{2}=\emptyset$.
Moreover, since $A_{1}\not=A_{2}$, we can assume without loss of generality
that $A_{2}$ is not the empty set.

Now we choose, uniformly at random, the sequence $\Sigma^{\prime}$ with
elements in $[1,M]^{k}$ and of length $n^{\prime}$ (whose value will be
specified later). Let $X$ be a random variable that represents the numbers of
pairs of elements of $\mathcal{F}_{\lambda,n^{\prime}}$ such that $A_{1}\cap
A_{2}=\emptyset$, $S(A_{1})=S(A_{2})$ and $A_{2}$ is not the empty set.

Then we need to estimate the following expected value

$\displaystyle\mathbb{E}[X]$
$\displaystyle=\mathbb{E}(|\\{\\{A_{1},A_{2}\\}:S(A_{1})=S(A_{2}),A_{1},A_{2}\in\mathcal{F}_{\lambda,n^{\prime}},A_{1}\cap
A_{2}=\emptyset\not=A_{2}\\}|)$ $\displaystyle=\sum_{\\{A_{1},A_{2}\\}:\
A_{1},A_{2}\in\mathcal{F}_{\lambda,n^{\prime}},A_{1}\cap
A_{2}=\emptyset\not=A_{2}}p[S(A_{1})=S(A_{2})].$

Since $A_{1}\cap A_{2}=\emptyset$, the value of $S(A_{1})$ is independent from
the value of $S(A_{2})$. Then the probability $p[S(A_{1})=S(A_{2})]$ is the
following

$p[S(A_{1})=S(A_{2})]=\sum_{s\in\mathbb{Z}^{k}}p[S(A_{1})=s]\cdot
p[S(A_{2})=s].$

We recall that $A_{1}\cap A_{2}=\emptyset\not=A_{2}$ and hence there exists
$i\in A_{2}\setminus A_{1}$. Clearly, $A_{2}$ can sum to $s$ only if
$a_{i}=s-S(A_{2}\setminus\\{i\\})$ that happens with probability at most
$1/M^{k}$. This means that

$\displaystyle\mathbb{E}[X]$ $\displaystyle\leq\sum_{\\{A_{1},A_{2}\\}:\
A_{1},A_{2}\in\mathcal{F}_{\lambda,n},A_{1}\cap
A_{2}=\emptyset\not=A_{2}}\left(\sum_{s\in\mathbb{Z}^{k}}p[S(A_{1})=s](1/M^{k})\right)$
$\displaystyle=\frac{1}{M^{k}}|\\{\\{A_{1},A_{2}\\}:\
A_{1},A_{2}\in\mathcal{F}_{\lambda,n},A_{1}\cap
A_{2}=\emptyset\not=A_{2}\\}|.$

Therefore, according to Lemma 3.14, we have that

(14) $\mathbb{E}[X]<\frac{1}{M^{k}}(\lambda n^{\prime})^{2}\cdot
2^{f(\lambda)n^{\prime}-1}.$

This means that, in case $(1/M^{k})(\lambda n^{\prime})^{2}\cdot
2^{f(\lambda)n^{\prime}-1}\leq t$, there exists a sequence
$\Sigma^{\prime}=(a_{1},\dots,a_{n^{\prime}})$ of elements in $\mathbb{Z}^{k}$
with at most $t$ pairs $\\{A_{1},A_{2}\\}$ that have the same sum and satisfy
the assumptions. Hence, we can remove $t$ elements from $\Sigma^{\prime}$ and
obtain a new sequence $\Sigma=(a_{1},\dots,a_{n})$, with $n=n^{\prime}-t$
elements, that is $\mathcal{F}_{\lambda,n}$-sum distinct. Since
$n^{\prime}=n+t$ and due to inequality (14), $\Sigma$ exists whenever

(15)
$M\geq(1+o(1))\sqrt[k]{\frac{\lambda^{2}n^{2}}{2}\frac{2^{f(\lambda)t}}{t}}\cdot
2^{f(\lambda)n/k}.$

It can be seen that the function $g_{\lambda}(t):=\frac{2^{f(\lambda)t}}{t}$
is strictly convex for $t>0$ and the minimum integer $m$ for which
$g_{\lambda}(m+1)\geq g_{\lambda}(m)$ is equal to $\tau_{\lambda}$. Therefore
$t=\tau_{\lambda}=\left\lceil\frac{1}{2^{f(\lambda)}-1}\right\rceil$ is the
best choice in order to optimize the inequality (15). ∎

######  Remark 3.16.

We note that for $k=1$ and $n$ sufficiently large the upper bound given in
Theorem 3.3 improves the one given in Theorem 3.15 since

$\lambda<\frac{2^{f(\lambda)\tau_{\lambda}}}{2\tau_{\lambda}}\,,$

for every $0<\lambda\leq 1/3$.

(a) $k=1$ (b) $k>1$

Figure 5. Exponent of the upper and lower bounds for $k=1$ and for $k>1$. Here
the bounds of Bohman [6], Theorem 3.3 and Theorem 3.12 have been extended via
Proposition 3.13.

##  4\. Conclusions

In this paper, we investigated a generalization of the Erdős sum-distinct
problem by weakening the constraint to the family of subsets
$\mathcal{F}_{\lambda,n}$ and working in $\mathbb{Z}^{k}$. We believe that
other variations (that are in the same spirit of the problem studied in [4])
are also worth considering, such as the following:

  * 1)

$\mathcal{F}$ can be taken as a subfamily of $\mathcal{P}([1,n])$ of a given
cardinality, for example when $\mathcal{F}$ is the family of subsets of
$[1,n]$ of size $n/2$;

  * 2)

$\mathcal{F}$ can be taken as the family of sets of size at most $m$ (see also
[10] for a similar problem with $m=2$);

  * 3)

each integer is allowed to be covered at most $t$ times by the sums of
$\mathcal{F}$.

Several of our constructions can be easily adapted to one or more of those
situations (for example the probabilistic one works in all those cases).
However, no deep idea is needed in this adaptation and, for now, we prefer to
keep the treatment more simple and clear. Nevertheless, we plan to investigate
those problems more carefully in the future.

## References

  * [1] I. Aliev, Siegel’s lemma and sum-distinct sets, Discrete Comput. Geom. 39 (2008), 59-66.
  * [2] N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), 7-29.
  * [3] N. Alon and J. H. Spencer, The probabilistic method, 4th ed. Wiley, Hoboken, NJ, 2016.
  * [4] M. Axenovich, Y. Caro, R. Yuster, Sum-distinguishing number of sparse hypergraphs, Preprint (Arxiv: 2102.02487).
  * [5] J. Bae, On subset-sum-distinct sequences. Analytic number theory, Vol. 1, Progr. Math., 138, Birkhauser, Boston, 1996, 31-37.
  * [6] T. Bohman, A construction for sets of integers with distinct subset sums, Electron. J. Combin. 5 (1998), Research Paper 3, 14 pages.
  * [7] S. Costa, F. Morini, A. Pasotti, M.A. Pellegrini, A problem on partial sums in abelian groups, Discrete Math. 341 (2018), 705-712.
  * [8] S. Costa, M.A. Pellegrini, Some new results about a conjecture by Brian Alspach, Archiv der Mathematik 115 (2020), 479-488.
  * [9] I. Csiszár and P.C. Shields, Information Theory and Statistics: A Tutorial, Foundations and Trends in Communications and Information Theory: Vol. 1: No. 4, 417-528, (2004).
  * [10] S. Della Fiore, M. Dalai, A note on $\overline{2}$-separable codes and $B_{2}$ codes, Disc. Math. 343 (2022).
  * [11] N. D. Elkies, An improved lower bound on the greatest element of a sum-distinct set of fixed order, J. Combin. Theory Ser. A 41 (1986), 89-94.
  * [12] P. Erdős, Problems and results in additive number theory, Colloque sur la Theorie des Nombres, Bruxelles, 1955, 127-137.
  * [13] Quentin Dubroff, Jacob Fox and Max Wenqiang Xu, A note on the Erdős distinct subset sums problem, SIAM J. Discret. Math. 35 (2021), 322-324.
  * [14] R. K. Guy, Sets of integers whose subsets have distinct sums, Theory and practice of combinatorics, 141–154, North-Holland Math. Stud., 60, Ann. Discrete Math., 12, North-Holland, Amsterdam, (1982).
  * [15] R. K. Guy, Unsolved Problems in Intuitive Mathematics, Vol. I, Number Theory, Problem C8, Springer-Verlag (1981).
  * [16] L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory 1 (1966), 385-393.
  * [17] J. Hicks, M.A. Ollis, J.R. Schmitt, Distinct partial sums in cyclic groups: polynomial method and constructive approaches, J. Combin. Des. 27 (2019), 369-385.
  * [18] D. J. Kleitman, Extremal hypergraph problems. Surveys in combinatorics, Proc. Seventh British Combinatorial Conf., Cambridge, (1979), 4465, London Math. Soc. Lecture Note Ser., 38, Cambridge Univ. Press, Cambridge-New York, (1979).
  * [19] László Györfi, Sándor Győri, Bálint and Laczay Miklós Ruszinkó, Lectures on Multiple Access Channels, Web: http://www.szit.bme.hu/gyori/AFOSR.
  * [20] W.F. Lunnon, Integer sets with distinct subset sums, Math. Compute, 50 (1988) 297-320.
  * [21] I. G. Shevtsova, An improvement of convergence rate estimates in the Lyapunov theorem, Dokl. Math. 82 (2010), 862-864.


††thanks: Corresponding author. Email address<EMAIL_ADDRESS>
# Probabilistic Dense Coding Using Non-Maximally Entangled Three-Particle
State

ZHANG Guo-Hua, YAN Feng-Li  College of Physics Science and Information
Engineering, Hebei Normal University, Shijiazhuang 050016, China;
Hebei Advanced Thin Films Laboratory, Shijiazhuang 050016, China

###### Abstract

We present a scheme of probabilistic dense coding via a quantum channel of
non-maximally entangled three-particle state. The quantum dense coding will be
succeeded with a certain probability if the sender introduces an auxiliary
particle and performs a collective unitary transformation. Furthermore, the
average information transmitted in this scheme is calculated.

###### pacs:

03.65.Ta, 03.67.Hk, 03.67.Lx

One of the essential features of quantum information is its capacity for
entanglement. The present-day entanglement theory has its roots in the key
discoveries: quantum teleportation,[1] quantum cryptography with Bell
theorem,[2] and quantum dense coding.[3] Entanglement has also played
important role in development of quantum computation and quantum
communication. [4-7]

Holevo has shown that one qubit can carry at most only one bit of classical
information. [8] In 1992, Bennett and Wiesner discovered a fundamental
primitive, quantum dense coding, [3] which allows to communicate two classical
bits by sending one a priori entangled qubit. Quantum dense coding is one of
many surprising applications of quantum entanglement. In 1996, quantum dense
coding was experimentally demonstrated with polarization entangled photons for
the case of discrete variables by Mattle et al. [9] Recent years, some schemes
for quantum dense coding using multi-particle entangled states via local
measurements,[10] GHZ state,[11] non-symmetric quantum channel [12] were
proposed. Liu et al.[13] presented the general scheme for dense coding between
multi-parties using a high-dimensional state. All these cases deal with
maximally entangled states.

Recently, Hao et al.[14] gave a probabilistic dense coding scheme using the
two-qubit pure state $|\phi\rangle=a|00\rangle+b|11\rangle$. A general
probabilistic dense coding scheme was put forward by Wang et al [15].

In this Letter, we suggest a scheme of probabilistic dense coding via a
quantum channel of non-maximally entangled three-particle state. The average
information transmitted in the scheme is calculated. Furthermore, the scheme
is generalized to $d$-level $(d>3)$ for three parties.

We first consider the dense coding between three-parties (Alice, Bob and
Charlie) via a maximally entangled three-particle state. Suppose Alice and Bob
are the senders, Charlie is the receiver, a maximally entangled three-particle
state

$|\psi_{00}\rangle_{ABC}=\frac{1}{\sqrt{3}}(|000\rangle+|111\rangle+|222\rangle)_{ABC}$
(1)

is shared by them, and the three particles $A$, $B$ and $C$ are held by Alice,
Bob and Charlie, respectively.

Let us introduce the nine single-particle operations as follows:

$\begin{array}[]{ll}U_{00}=\left(\begin{array}[]{ccc}1&0&0\\\ 0&1&0\\\
0&0&1\end{array}\right),&U_{01}=\left(\begin{array}[]{ccc}1&0&0\\\ 0&e^{2\pi
i/3}&0\\\ 0&0&e^{4\pi i/3}\end{array}\right),\\\
U_{02}=\left(\begin{array}[]{ccc}1&0&0\\\ 0&e^{4\pi i/3}&0\\\ 0&0&e^{2\pi
i/3}\end{array}\right),&U_{10}=\left(\begin{array}[]{ccc}0&0&1\\\ 1&0&0\\\
0&1&0\end{array}\right),\\\ U_{11}=\left(\begin{array}[]{ccc}0&0&e^{4\pi
i/3}\\\ 1&0&0\\\ 0&e^{2\pi
i/3}&0\end{array}\right),&U_{12}=\left(\begin{array}[]{ccc}0&0&e^{2\pi i/3}\\\
1&0&0\\\ 0&e^{4\pi i/3}&0\end{array}\right),\\\
U_{20}=\left(\begin{array}[]{ccc}0&1&0\\\ 0&0&1\\\
1&0&0\end{array}\right),&U_{21}=\left(\begin{array}[]{ccc}0&e^{2\pi i/3}&0\\\
0&0&e^{4\pi i/3}\\\ 1&0&0\end{array}\right),\\\
U_{22}=\left(\begin{array}[]{ccc}0&e^{4\pi i/3}&0\\\ 0&0&e^{2\pi i/3}\\\
1&0&0\end{array}\right).\end{array}$ (2)

It is easy to prove that

$\displaystyle U_{00}(A)\otimes U_{00}(B)|\psi_{00}\rangle_{ABC}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{3}}(|000\rangle+|111\rangle+|222\rangle)_{ABC}\equiv|\psi^{0}_{00}\rangle_{ABC},$
$\displaystyle U_{00}(A)\otimes U_{10}(B)|\psi_{00}\rangle_{ABC}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{3}}(|010\rangle+|121\rangle+|202\rangle)_{ABC}\equiv|\psi^{0}_{01}\rangle_{ABC},$
$\displaystyle U_{00}(A)\otimes U_{20}(B)|\psi_{00}\rangle_{ABC}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{3}}(|020\rangle+|101\rangle+|212\rangle)_{ABC}\equiv|\psi^{0}_{02}\rangle_{ABC},$
$\displaystyle U_{01}(A)\otimes U_{00}(B)|\psi_{00}\rangle_{ABC}$
$\displaystyle=$ $\displaystyle\frac{1}{\sqrt{3}}(|000\rangle+e^{2\pi
i/3}|111\rangle+e^{4\pi
i/3}|222\rangle)_{ABC}\equiv|\psi^{0}_{10}\rangle_{ABC},$ $\displaystyle
U_{01}(A)\otimes U_{10}(B)|\psi_{00}\rangle_{ABC}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{3}}(|010\rangle+e^{2\pi i/3}|121\rangle+e^{4\pi
i/3}|202\rangle)_{ABC}\equiv|\psi^{0}_{11}\rangle_{ABC},$
$\displaystyle\cdots,$ $\displaystyle U_{22}(A)\otimes
U_{20}(B)|\psi_{00}\rangle_{ABC}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{3}}(|220\rangle+e^{4\pi i/3}|001\rangle+e^{2\pi
i/3}|112\rangle)_{ABC}\equiv|\psi^{2}_{22}\rangle_{ABC}$

and
$\\{|\psi^{0}_{00}\rangle,|\psi^{0}_{01}\rangle,|\psi^{0}_{02}\rangle,|\psi^{0}_{10}\rangle,|\psi^{0}_{11}\rangle,\cdots,|\psi^{2}_{22}\rangle\\}$
is a basis of the Hilbert space of the particles $A$, $B$ and $C$.

Alice performs one of the nine unitary transformations stated in Eq.(2) on
particle $A$, Bob operates one of three unitary transformations
$U_{00},U_{10},U_{20}$, on particle $B$. Then they send their particles $A$
and $B$ to the receiver Charlie. After receiving the particles $A$ and $B$,
Charlie takes only one measurement in the basis
$\\{|\psi^{0}_{00}\rangle,|\psi^{0}_{01}\rangle,|\psi^{0}_{02}\rangle,|\psi^{0}_{10}\rangle,|\psi^{0}_{11}\rangle,\cdots,|\psi^{2}_{22}\rangle\\}$,
and she will know what operation Alice and Bob have carried out, that is, what
messages are that Alice and Bob have encoded in the quantum state. Then
Charlie can obtain ${\rm log}_{2}27$ bits of information through only one
measurement. So the dense coding is realized successfully.

In the following we will discuss a scheme of probabilistic dense coding
between three parties via a non-maximally entangled three-particle state. We
suppose that Alice, Bob and Charlie share a non-maximally entangled three-
particle state

$|\varphi\rangle_{ABC}=(x_{0}|000\rangle+x_{1}|111\rangle+x_{2}|222\rangle)_{ABC},$
(4)

where $x_{0},x_{1},x_{2}$ are real numbers, and
$|x_{0}|^{2}+|x_{1}|^{2}+|x_{2}|^{2}=1$. Without loss of generality, we can
suppose that $|x_{0}|\leq|x_{1}|\leq|x_{2}|$.

The scheme of probabilistic dense coding is composed of four steps.

Firstly, Alice introduces an auxiliary three-level particle $a$ in the quantum
state $|0\rangle_{a}$. Then she performs a unitary transformation $U_{sim}$ on
her particle A and auxiliary particle $a$ under the basis
$\\{|00\rangle_{Aa},|01\rangle_{Aa},|02\rangle_{Aa},|10\rangle_{Aa},|11\rangle_{Aa},|12\rangle_{Aa},|20\rangle_{Aa},$
$|21\rangle_{Aa},|22\rangle_{Aa}\\}$:

$U_{sim}=\left(\begin{array}[]{ccccccccc}1&0&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0&0\\\ 0&0&0&m_{01}&m&0&0&0&0\\\
0&0&0&m&-m_{01}&0&0&0&0\\\ 0&0&0&0&0&m_{02}&0&M&-N\\\
0&0&0&0&0&0&m_{02}&N&M\\\ 0&0&0&0&0&M&N&-m_{02}&0\\\
0&0&0&0&0&-N&M&0&-m_{02}\\\ \end{array}\right),$ (5)

where
$M=\sqrt{(x^{2}_{2}-x^{2}_{1})/x_{2}^{2}},N=\sqrt{(x^{2}_{1}-x^{2}_{0})/x_{2}^{2}},m=\sqrt{1-x^{2}_{0}/x_{1}^{2}},m_{01}=x_{0}/x_{1},m_{02}=x_{0}/x_{2}$.
The collective unitary operator $U_{sim}\otimes I_{BC}$ (where $I_{BC}$ is a
$9\times 9$ identity matrix) transforms the state
$|\varphi\rangle_{ABC}\otimes|0\rangle_{a}$ into

$\displaystyle|\varphi^{\prime}\rangle_{ABCa}$ $\displaystyle=$ $\displaystyle
U_{sim}\otimes I_{BC}|\varphi\rangle_{ABC}\otimes|0\rangle_{a}$
$\displaystyle=$
$\displaystyle\sqrt{3}x_{0}\frac{1}{\sqrt{3}}(|000\rangle+|111\rangle+|222\rangle)_{ABC}|0\rangle_{a}$
$\displaystyle+\sqrt{2}\sqrt{x_{1}^{2}-x_{0}^{2}}\frac{1}{\sqrt{2}}(|111\rangle+|222\rangle)_{ABC}|1\rangle_{a}$
$\displaystyle+\sqrt{x_{2}^{2}-x_{1}^{2}}|222\rangle_{ABC}|2\rangle_{a}$
$\displaystyle\equiv$
$\displaystyle\sqrt{3}x_{0}|\varphi_{00}\rangle_{ABC}|0\rangle_{a}+\sqrt{2}\sqrt{x_{1}^{2}-x_{0}^{2}}|\varphi^{\prime}_{00}\rangle_{ABC}|1\rangle_{a}$
$\displaystyle+\sqrt{x_{2}^{2}-x_{1}^{2}}|\varphi^{\prime\prime}_{00}\rangle_{ABC}|2\rangle_{a}.$

Then Alice makes a measurement on the auxiliary particle $a$ and tells Bob and
Charlie her measurement result via a classical channel. If she gets the result
$|0\rangle_{a}$, she ensures that the three particles $A$, $B$ and $C$ are in
the maximally entangled three-particle state
$|\varphi_{00}\rangle=\frac{1}{\sqrt{3}}(|000\rangle+|111\rangle+|222\rangle)$,
the probability of obtaining $|0\rangle_{a}$ is $3x_{0}^{2}$ according to
Eq.(6); if the result $|1\rangle_{a}$ is obtained, she ensures that the three
particles $A$, $B$ and $C$ are in the state
$|\varphi^{\prime}_{00}\rangle=\frac{1}{\sqrt{2}}(|111\rangle+|222\rangle)$,
and the probability of getting this result is $2(x_{1}^{2}-x_{0}^{2})$; if she
gets the result $|2\rangle_{a}$, she knows that the three particles are in the
product state $|\varphi^{\prime\prime}_{00}\rangle=|222\rangle$, and the
probability of obtaining this result is $x_{2}^{2}-x_{1}^{2}$.

Secondly, Alice and Bob encode classical information by performing the unitary
transformations on their particle $A$ and $B$ respectively.

If the three particles $A$, $B$ and $C$ are in the state
$|\varphi_{00}\rangle=\frac{1}{\sqrt{3}}(|000\rangle+|111\rangle+|222\rangle)$,
one uses the dense coding protocol stated above. Here we do not recite any
more.

If the three particles $A$, $B$ and $C$ are in the state
$|\varphi^{\prime}_{00}\rangle=\frac{1}{\sqrt{2}}(|111\rangle+|222\rangle)$,
Alice encodes her message by performing one of six single-particle operations

$\begin{array}[]{ll}U^{\prime}_{00}=\left(\begin{array}[]{ccc}1&0&0\\\
0&1&0\\\
0&0&1\end{array}\right),&U^{\prime}_{01}=\left(\begin{array}[]{ccc}1&0&0\\\
0&1&0\\\ 0&0&-1\end{array}\right),\\\
U^{\prime}_{10}=\left(\begin{array}[]{ccc}0&0&1\\\ 1&0&0\\\
0&1&0\end{array}\right),&U^{\prime}_{11}=\left(\begin{array}[]{ccc}0&0&-1\\\
1&0&0\\\ 0&1&0\end{array}\right),\\\
U^{\prime}_{20}=\left(\begin{array}[]{ccc}0&1&0\\\ 0&0&1\\\
1&0&0\end{array}\right),&U^{\prime}_{21}=\left(\begin{array}[]{ccc}0&1&0\\\
0&0&-1\\\ 1&0&0\end{array}\right)\end{array}$ (7)

on particle $A$. However, Bob encodes his message only by operating one of
three single-particle operations $U^{\prime}_{00}$, $U^{\prime}_{10}$,
$U^{\prime}_{20}$ on particle $B$. Through simple calculation, we can prove
that

$\displaystyle U^{\prime}_{00}(A)\otimes
U^{\prime}_{00}(B)|\varphi^{\prime}_{00}\rangle_{ABC}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|111\rangle+|222\rangle)_{ABC}\equiv|\varphi^{\prime
0}_{00}\rangle_{ABC},$ $\displaystyle U^{\prime}_{00}(A)\otimes
U^{\prime}_{10}(B)|\varphi^{\prime}_{00}\rangle_{ABC}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|121\rangle+|202\rangle)_{ABC}\equiv|\varphi^{\prime
1}_{00}\rangle_{ABC},$ $\displaystyle U^{\prime}_{00}(A)\otimes
U^{\prime}_{20}(B)|\varphi^{\prime}_{00}\rangle_{ABC}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|101\rangle+|212\rangle)_{ABC}\equiv|\varphi^{\prime
2}_{00}\rangle_{ABC},$ $\displaystyle U^{\prime}_{01}(A)\otimes
U^{\prime}_{00}(B)|\varphi^{\prime}_{00}\rangle_{ABC}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|111\rangle-|222\rangle)_{ABC}\equiv|\varphi^{\prime
0}_{01}\rangle_{ABC},$ $\displaystyle\cdots,$ $\displaystyle
U^{\prime}_{21}(A)\otimes
U^{\prime}_{20}(B)|\varphi^{\prime}_{00}\rangle_{ABC}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|001\rangle-|112\rangle)_{ABC}\equiv|\varphi^{\prime
2}_{21}\rangle_{ABC}.$

It is easy to see that the states in the set $\\{|\varphi^{\prime
k}_{mn}\rangle,m,k=0,1,2;n=0,1\\}$ are orthogonal each other.

If the three particles $A$, $B$ and $C$ are in the product state
$|\varphi^{\prime\prime}_{00}\rangle=|222\rangle$, Alice and Bob can encode
their classical information by performing one of three single-particle
operations on particles $A$ and $B$ independently:

$\begin{array}[]{ll}U^{\prime\prime}_{00}=\left(\begin{array}[]{ccc}1&0&0\\\
0&1&0\\\
0&0&1\end{array}\right),&U^{\prime\prime}_{10}=\left(\begin{array}[]{ccc}0&0&1\\\
1&0&0\\\ 0&1&0\end{array}\right),\\\
U^{\prime\prime}_{20}=\left(\begin{array}[]{ccc}0&1&0\\\ 0&0&1\\\
1&0&0\end{array}\right).\end{array}$ (9)

The state $|\varphi^{\prime\prime}_{00}\rangle$ will be transformed into the
corresponding state respectively:

(10) $\displaystyle U^{\prime\prime}_{00}(A)\otimes
U^{\prime\prime}_{00}(B)|\varphi^{\prime\prime}_{00}\rangle_{ABC}=|222\rangle_{ABC}\equiv|\varphi^{\prime\prime}_{00}\rangle_{ABC},$
$\displaystyle U^{\prime\prime}_{00}(A)\otimes
U^{\prime\prime}_{10}(B)|\varphi^{\prime\prime}_{00}\rangle_{ABC}=|202\rangle_{ABC}\equiv|\varphi^{\prime\prime}_{01}\rangle_{ABC},$
$\displaystyle U^{\prime\prime}_{00}(A)\otimes
U^{\prime\prime}_{20}(B)|\varphi^{\prime\prime}_{00}\rangle_{ABC}=|212\rangle_{ABC}\equiv|\varphi^{\prime\prime}_{02}\rangle_{ABC},$
$\displaystyle U^{\prime\prime}_{10}(A)\otimes
U^{\prime\prime}_{00}(B)|\varphi^{\prime\prime}_{00}\rangle_{ABC}=|022\rangle_{ABC}\equiv|\varphi^{\prime\prime}_{10}\rangle_{ABC},$
$\displaystyle\cdots,$ $\displaystyle U^{\prime\prime}_{20}(A)\otimes
U^{\prime\prime}_{20}(B)|\varphi^{\prime\prime}_{00}\rangle_{ABC}=|112\rangle_{ABC}\equiv|\varphi^{\prime\prime}_{22}\rangle_{ABC}.$

Evidently, the states in the set
$\\{|\varphi^{\prime\prime}_{mn}\rangle,m,n=0,1,2\\}$ are orthogonal each
other.

Thirdly, Alice and Bob send their particles $A$ and $B$ independently to
Charlie.

Finally, After Charlie receives particle $A$ and $B$, she takes only one
measurement on the three particle $A$, $B$ and $C$. The measurement basis is
determined by Alice’s measurement result. According to Charlie’s measurement
result, Charlie will know what operators Alice and Bob have carried out, i.e.
he can obtain the classical information that Alice and Bob have encoded.

Apparently, the average information transmitted in this procedure is

$I_{aver}=3x_{0}^{2}{\rm log}_{2}27+2(x_{1}^{2}-x_{0}^{2}){\rm
log}_{2}18+(x_{2}^{2}-x_{1}^{2}){\rm log}_{2}9.$ (11)

In fact, the above protocol needs $2{\rm log}_{2}3$ bits of classical
information for Alice to tell Bob and Charlie her measurement result on the
auxiliary particle. Obviously, when $x_{0}=x_{1}=x_{2}=\frac{1}{\sqrt{3}}$,
the three particles $A$, $B$ and $C$ is in the maximally entangled three-
particle state, and the success probability of dense coding is one. The
average information transmitted is ${\rm log}_{2}27$ bits.

Now we would like to generalize the above protocol to $d$-level for three
parties. Suppose that Alice, Bob and Charlie share a non-maximally entangled
three-particle state

$|\varphi\rangle_{ABC}=(x_{0}|000\rangle+x_{1}|111\rangle+\cdots+x_{d-1}|d-1d-1d-1\rangle)_{ABC},$
(12)

where $x_{0},x_{1},\cdots,x_{d-1}$ are real numbers and satisfy
$|x_{0}|\leq|x_{1}|\leq\cdots\leq|x_{d-1}|$.

The scheme of the probabilistic dense coding can be accomplished by four
steps.

(1) Alice introduces an auxiliary $d$-level particle in the quantum state
$|0\rangle_{a}$. Then she performs a proper unitary transformation on her
particle $A$ and the auxiliary particle. The collective unitary transformation
$U_{sim}\otimes I_{BC}$ (where $I_{BC}$ is a $d^{2}\times d^{2}$ identity
matrix) transforms the state $|\varphi\rangle_{ABC}\otimes|0\rangle_{a}$ into
the state

$\displaystyle|\varphi\rangle_{ABCa}$ $\displaystyle=$ $\displaystyle
x_{0}(|000\rangle+|111\rangle+\cdots+|d-1d-1d-1\rangle)_{ABC}|0\rangle_{a}$
$\displaystyle+\sqrt{x_{1}^{2}-x_{0}^{2}}(|111\rangle+\cdots+|d-1d-1d-1\rangle)_{ABC}|1\rangle_{a}$
$\displaystyle+\cdots+\sqrt{x_{d-1}^{2}-x_{d-2}^{2}}|d-1d-1d-1\rangle_{ABC}|d-1\rangle_{a}.$

After that Alice performs a measurement on the auxiliary particle. The
resulting state of the particles $A$, $B$ and $C$ will be respectively

$\frac{1}{\sqrt{d}}(|000\rangle+|111\rangle+\cdots+|d-1d-1d-1\rangle),$

$\frac{1}{\sqrt{d-1}}(|111\rangle+\cdots+|d-1d-1d-1\rangle),$

$\cdots,$

$|d-1d-1d-1\rangle$.
The probability of obtaining each resulting state is $dx_{0}^{2}$,
$(d-1)(x_{1}^{2}-x_{0}^{2}),\cdots,(x_{d-1}^{2}-x_{d-2}^{2})$, respectively.

(2) Alice tells Bob and Charlie her measurement result, then Alice and Bob
encode classical information by making a unitary transformation on particle
$A$ and $B$ respectively.

(3) Alice and Bob send particle $A$ and $B$ to Charlie respectively.

(4) After Charlie receives the particles $A$ and $B$, she takes a measurement
in the basis determined by Alice’s measurement result. According to his
measurement result, Charlie can obtain the classical information that Alice
and Bob have encoded. The average information transmitted is

$\displaystyle I_{aver}$ $\displaystyle=$ $\displaystyle dx_{0}^{2}{\rm
log}_{2}d^{3}+(d-1)(x_{1}^{2}-x_{0}^{2}){\rm log}_{2}d^{2}(d-1)$
$\displaystyle+(d-2)(x_{2}^{2}-x_{1}^{2}){\rm log}_{2}d^{2}(d-2)+\cdots$
$\displaystyle+(x_{d-1}^{2}-x_{d-2}^{2}){\rm log}_{2}d^{2}.$

Obviously, this probabilistic dense coding scheme needs $2{\rm log}_{2}d$ bits
of information to transmit Alice’s measurement results on the auxiliary
particle to Bob and Charlie.

It is easy to see that if the non-zero coefficients in Eq.(12) are totally
equal, Alice does not need to introduce the auxiliary particle and makes
unitary transformation $U_{sim}$. The classical information can be encoded
directly by performing single-particle operations on particle $A$ and $B$
respectively. In this case the quantum state is called a deterministic quantum
channel; otherwise, a probabilistic one if the coefficients are not equal
totally. Obviously, a non-maximally entangled three-particle state is not
equivalent to the probabilistic quantum channel. For example, in the $3\otimes
3\otimes 3$-dimensional case, the quantum state
$\frac{1}{\sqrt{2}}(|111\rangle+|222\rangle)$ is not a maximally entangled
three-particle state, but it is a deterministic quantum channel. So the first
step in our protocol is to extract a series of deterministic quantum channels
from a probabilistic one.

In summary, we have presented a scheme of probabilistic dense coding via a
quantum channel of non-maximally entangled three-particle state. The average
information transmitted in this scheme is explicitly given. We also generalize
this scheme to the more general case.

Acknowledgments

This work was supported by the National Natural Science Foundation of China
under Grant No: 10671054, Hebei Natural Science Foundation of China under
Grant No: 07M006 and the Key Project of Science and Technology Research of
Education Ministry of China under Grant No:207011.

## References

  * (1) Bennett C H et al 1993 _Phys. Rev. Lett._ 70 1895
  * (2) Ekert A K 1991 _Phys. Rev. Lett._ 67 661
  * (3) Bennett C H and Wiesner S J 1992 _Phys. Rev. Lett._ 69 2881
  * (4) Raussendorf R and Briegel H J 2001 _Phys. Rev. Lett._ 86 5188
  * (5) Wang X B, Hiroshima T, Tomita A and Hayashi M 2007 _Phys. Rep._ 448 1
  * (6) Long G L, Deng F G, Wang C, Li X H, Wen K and Wang W Y 2007 _Front. Phys. China_ 2 251
  * (7) Gao T, Yan F L and Li Y C 2008 _Europhys. Lett._ 84 50001
  * (8) Holevo A S 1973 _Probl. Peredachi Inf._ 9 3
  * (9) Mattle K, Weinfurter H, Kwiat P G and Zeilinger A 1996 _Phys. Rev. Lett._ 76 4656
  * (10) Chen J L and Kuang L M 2004 _Chin. Phys. Lett._ 21 12
  * (11) Hao J C, Li C F and Guo G C 2000 _Phys. Rev. A_ 63 054301
  * (12) Yan F L and Wang M Y 2004 _Chin. Phys. Lett._ 21 1195
  * (13) Liu X S, Long G L, Tong D M and Li F 2002 _Phys. Rev. A_ 65 022304
  * (14) Hao J C, Li C F and Guo G C 2000 _Phys.Lett. A_ 278 113
  * (15) Wang M Y, Yang L G and Yan F L 2005 _Chin. Phys. Lett._ 22 1053