Search

Dissociated sets avoiding geometric progressions

In a recent preprint, I dealt with sets with distinct subset sums. A set $\mathcal S\subset \mathbb N$ is said to be a subset-sum-distinct or dissociated (when studied in other contexts) if all of its finite subsets have different sums. Alternately, an equivalent classification is if any equality of the form
$$\sum_{s\in \mathcal S} \varepsilon_s \cdot s =0$$
where $\varepsilon_s \in \{-1,0,+1\}$ implies that all the $\varepsilon_s$'s are $0$.

Some two and a half years ago, I was playing around with the greedy algorithm on these sets, and noticed something strange. This starts with two given integers $a>0$ and $b>a$. It sets $\gamma_1=a$, $\gamma_2=b$ and in the $r$-th step it chooses $\gamma_r$ to be the smallest integer greater than $\gamma_{r-1}$ such that the sequence $\{\gamma_k\}_{k=1}^r$ is dissociated. For any given $a,b$, let $\Gamma:=\Gamma_{a,b}=\{\gamma_1=a, \gamma_2=b, \gamma_3, \dots \}$ be the dissociated sequence that the greedy algorithm produces. From purely numerical experiments, I noticed that there is always an $n_0=n_0(a,b)$ such that
$$\gamma_n = 2\cdot \gamma_{n-1}$$
for all $n\ge n_0$. I had to wait all this time to finally be able to prove this. One can see the proof in the preprint.

From this result (and some other observations I made in and outside the preprint), I thought that a large dissociated set must contain a lot of geometric progressions. In the preprint, I answered this in the negative by constructing a large collection of dissociated sets which also do not contain any three $a,b,c$ with $b^2=ac$. In this post, I will give an explicit nice construction of such a set.

First of all, note that for a dissociated set $\mathcal S$, we have
$$\left\vert\mathcal S(n)\right\vert \le \log_2 n + \mathcal{O}( \log_2\log_2 n)$$
where $\mathcal S(n) := \mathcal S \cap [1,n]$. This is because the map $f : \mathcal P\left(\mathcal S(n)\right) \to \mathbb N$ that takes a subset of $\mathcal S(n)$ to the sum of its elements is injective, hence giving $2^{\left\vert\mathcal S(n)\right\vert} \leq n\cdot \left\vert\mathcal S(n)\right\vert +1$, hence completing the proof.

So, we will now construct a dissociated set of size $\sim \log_2 n$ that does not contain any GP.

Theorem : The sequence $\{\psi_n\}_{n=1}^\infty$ defined as
$$\psi_n = \frac{2^{n+2}}{7} + \frac{1}{7\sqrt 3}\cdot\sin \left(\frac{2\pi n}{3}\right) + \frac 37 \cdot \cos \left(\frac{2\pi n}{3}\right)$$
is dissociated and does not contain any three term geometric progression.

The proof of this follows from a series of simple and straightforward observations that we will list as Lemmas. We should of course begin with the obvious
Lemma 1 : The values of $\{\psi_n\}_{n=1}^\infty$ are given by
\begin{align*}&\psi_{3k} = \frac{4\cdot 8^k}{7} + \frac 37\\&\psi_{3k+1} = \frac{8^{k+1}}{7} - \frac 17\\&\psi_{3k+2} = \frac{2\cdot 8^{k+1}}{7} - \frac 27\end{align*}
for all $k$. So, $\psi_n$ is a positive integer, and can be expressed as
$$\psi_n = \left\lVert \frac{2^{n+2}}{7} \right\rVert$$
where $\lVert \cdot \rVert$ represents rounding to the nearest integer.

Proof : The expressions for $\psi_{3k+i}$, $i=0,1,2$ are a matter of straightforward computation. The fact that they are all integers follows from the simple observation that
$$8^k = \left(7+1\right)^k \equiv 1 \pmod 7$$
for all $k$. $\square$


Lemma 2 : The sequence $\{\psi_n\}_{n=1}^\infty$ is strictly increasing. In fact, we have
\begin{align*}&\psi_{3k} = 2\cdot \psi_{3k-1} + 1\\&\psi_{3k+1} = 2\cdot \psi_{3k} - 1\\&\psi_{3k+2} = 2\cdot \psi_{3k+1}\end{align*}
for all $k\in \mathbb N$. So,
$$\psi_n = \psi_{n-1}+\psi_{n-2}+2\cdot \psi_{n-3}$$
which admits
$$\frac 1{1 - x - x^2 - 2x^3} = \frac 1 {(1-2x)(1+x+x^2)}$$
as the generating function.

Proof : The expressions for $\psi_{3k+i}$, $i=0,1,2$ follow immediately from Lemma 1. This, used in an Induction argument, proves the recursion. The generating function is a simple consequence of it. $\square$


Lemma 3 : The sequence admits a nice modularity property. In particular
\begin{align*}&\psi_{3k} \equiv 5 \pmod 8\\&\psi_{3k+1} \equiv 1 \pmod 8\\&\psi_{3k+2} \equiv 2 \pmod 8\end{align*}
for all $k\in \mathbb N$.

Proof : We begin by calculating that $\psi_1=1$, $\psi_2=2$ and $\psi_3=5$. The rest of the proof is immediate from Lemma 2. $\square$

Lemma 4 : We have
$$\sum_{i=1}^m \psi_i < \psi_{m+1}$$
for all $m\in \mathbb N$, $m\ge 2$.

Proof :  Notice that the lemma is trivial to check for $m=2,3,4$.
Now, let us assume
$$\sum_{i=1}^k \psi_i < \psi_{k+1}$$
for some $k$. This gives
$$\sum_{i=1}^{k+1} \psi_i < 2\cdot\psi_{k+1}$$
and hence
$$\sum_{i=1}^{k+3} \psi_i < \psi_{k+4}$$
using the recursion discussed in Lemma 2.
So, an induction argument completes the proof. $\square$


Equipped with these lemmas, it is now possible to give a proof of the Theorem.

Proof : We will first show that the set is dissociated. To do so, let us assume that it's not. If possible, let there be indexing sets $\{i_k\}_{k=1}^n$ and $\{j_k\}_{k=1}^m$ such that
$$\psi_{i_1}+\dots \psi_{i_n} = \psi_{j_1}+\dots \psi_{j_m}$$
where all the $\psi_i$'s are distinct.

Without loss of generality, let $\psi_{i_1}$ be the largest of these $\psi_k$'s. By Lemma 4, this implies
$$\psi_{i_1} > \psi_{j_1}+\dots \psi_{j_m}$$
and hence
$$\psi_{i_1}+\dots \psi_{i_n} > \psi_{j_1}+\dots \psi_{j_m}$$
which is a contradiction.

Now, we wish to show that there are no three term geometric progressions in the sequence. On the contrary, let us assume
$$\psi_i^2 = \psi_j\cdot \psi_k$$
for some $\psi_i$, $\psi_j$, $\psi_k$ in our sequence. We begin by noticing that Lemma 3 implies that either
$$i,j,k \equiv 0,1,1 \pmod 3$$
or $i\equiv j\equiv k\pmod 3$.

For the first case, let us assume that there are integers $j,k,\ell\ge 2$ (the other cases can be checked by hand) such that
$$\psi_{3k}^2 = \psi_{3j+1} \cdot \psi_{3\ell +1}$$
which implies
$$\left(4\cdot 8^k + 3\right)^2 = \left(8^j-1\right)\cdot \left(8^\ell-1\right)$$
by Lemma 1. This is a contradiction since the LHS and the RHS are $9$ and $1$ modulo $64$ respectively.

Now, let us consider the case $i\equiv j\equiv k \equiv 0\pmod 3$. Again as before, we assume
$$\psi_{3k}^2 = \psi_{3j} \cdot \psi_{3\ell}$$
where without loss of generality, it may be assumed that $\ell<k<j$. By Lemma 1, we have
$$8^{2k+1}-8^{\ell+j+1} = 12\cdot \left(8^j + 8^\ell -8^k\right)$$
and hence
$$8^{2k+1-\ell} - 8^{j+1} = 12\times \left(8^{j-\ell} - 8^{k-\ell} + 1\right)$$
which is a contradiction since the LHS and RHS do not match modulo $8$.

The cases $i\equiv j\equiv k \equiv 1\pmod 3$ or $i\equiv j\equiv k \equiv 2\pmod 3$ are to be dealt similarly as the previous case. $\square$

Dissociated sets avoiding geometric progressions

In a recent preprint , I dealt with sets with distinct subset sums. A set $\mathcal S\subset \mathbb N$ is said to be a subset-sum-distinct ...