Set system with different differences

Question

What is the maximal number of sets in a set system $\mathcal{A}$ of subsets of an $n$ element set such that for every $i \neq j $ and $A_i,A_j \in \mathcal{A}$ the difference $A_i \setminus A_j$ is unique? (No other sets produce the same difference!)

Answer 1

Here is an idea of a proof that gives a family of subsets with exponential dependence on $n$ (not an answer, but too long for a comment.) (But the family is not explicitly constructed.)

First, consider the same problem with symmetric difference $$A_i\oplus A_j:=(A_i\setminus A_j)\cup (A_j\setminus A_i)$$ instead of the usual difference. Denote by $a_n$ the maximal number of sets in this problem. It is easy to see that $a_n$ grows exponentially, in the sense that $$\log(a_n)/n>C$$ for some $C>0$ (where $n>1$). This easily follows from

Lemma $$2^n\le a_n+{a_n\choose 3}.$$ Proof: Suppose we have a maximal collection of subsets $A_n$ of $\{1,...,n\}$. If there exists a subset $B$ such that $B$ is not in the list $$\{A_i\}, \{A_i\oplus A_j\oplus A_k\},$$ we can add it to the collection. QED.

Now I claim that the answer to the original question is at least $a_{[n/2]}$, essentially by Seva's argument. Namely, let $A_i$ be a maximal collection of subsets of $\{1,...,k\}$, $k=[n/2]$; construct a collection of subsets of $\{1,..,2k\}$ as $$A_i'=A_i\cup (k+(\{1,..,k\}\setminus A_i)),$$ where $+$ is the element-wise addition. That is, the first half of each subset $A_i'$ is the same as $A_i$, and the second half is the complement of $A_i$. It is clear that $A_i'\setminus A_j'$ allows us to reconstruct $A_i\oplus A_j$.

Answer 2

I had the same thought as Seva, and then it occurred to me that it is really a (somewhat trivial) combinatorial design of some sort.

Most of my thoughts on this problem are much easier to think up if I assume that the $A_i$ are all the same size (and likewise for all the $A_i\backslash A_j$). This is what makes me think of using some type of design.

What is most familiar to me is a Steiner system, e.g. the finite projective plane of size $n/2=q^2+q+1$. In this case, any pair of points (points are $[n]$) determines a line in the projective plane. In general, a Steiner $(t,k,n)$ system is a family of $k$-sized subsets (which would correspond to the $A_i$) of $[n]$ such that any $t$-sized subset of $n$ uniquely determines one of the $k$-sets in the family. The projective plane is a Steiner $(2,q+1,q^2+q+1)$ system of size $q+1$ (the number of points happens to be the number of lines, hence the repetition of $q+1$).

In Seva's example, the Steiner system is just the set ${i}$ for $1\le i\le n/2$. This is a Steiner $(1,1,n/2)$ system. He then couples each of those sets with its complement to make $A_j$ identifiable from $A_i\backslash A_j$.

So, assuming $n$ is of the right form, you can construct the $A_i$ in a similar way: each line (from the projective plane of size $n/2=q^2+q+1$) is coupled with its complement (shifted to the other half of $[n]$). This means $|A_i|=n/2$ and the set-system is size $q+1$ where $n/2=q^2+q+1$.

In this case, rearranging slightly tells us that you have a family of size $\sqrt{n/2}$ sets (lines). This is admittedly worse than Seva's simple example, but it is familiar and gives us the idea that Steiner systems might say something about the problem.

There are Steiner $(2,3,n)$ systems where each set has three elements, and there are $n(n-1)/6$ of these triples in the system. However, we will need to make sure that we can reconstruct $A_i$ from $A_i\backslash A_j$. Because $|A_i\cap A_j|\le 1$, we know $A_i\backslash A_j\ge 2$, which allows us to reconstruct $A_i$ from two of its elements.

Notice then, same as before, that this only tells us how to get $A_i$ from $A_i\backslash A_j$. We swap $n/2$ for $n$ (with the appropriate conditions on $n$) and conjoin each $A_i$ with its complement in $[n/2]$ shifted to fill the rest of $[n]$ as before. In this case, we have $(n/2)(n/2-1)/6\approx n^2/24$ sets of size 3 in the family.

It should be noted that there is a $(2,3,n)$ system for infinitely many (but not all) $n$, so this does work to create arbitrarily large examples.

Assuming you have a Steiner $(t,k,n)$ system, you need $t>k/2$ to allow us to recover $A_i$ from $A_i\backslash A_j$. There would be $\binom{n}{t}/\binom{k}{t}$ sets in the system. Stirling's approximation tells us that the size of the set system is bounded by $\left(\frac{1}{e^2k^2}\right)n^2$, which is quadratic as in the second example above. And then you'd have to divide by 4, since we're replacing $n\mapsto n/2$ to accommodate the recover of $A_j$ from $A_i\backslash A_j$. I've set $t=2$ because otherwise we can't guarantee the existence of these systems, and so it seems like you can't beat quadratic using this (very particular) type of construction.

If you could prove there are Steiner $(k-1,k,n)$ systems for arbitrarily large $n$ for any particular $k>3$, you would have a pretty great result right there in itself. But that would also give you the type of family you want of size $\left(\frac{1}{(2e)^{k-1}k^{k-1}}\right)n^{k-1}$. It is not clear whether we should expect such things to exist (and if so, for which values of $k$). I'm using $t=k-1$ because that's how all the open questions for Steiner systems seem to be phrased.

I'm not sure if this is really useful enough to be an "answer" or a "comment" but I am not active enough on this site to post a comment, so it will have to be an answer instead. (And then, feeling obligated, I filled out my response with details and comments as much as I thought useful.) It's really just a technical improvement on the basic idea that Seva mentions in his comment, and I'm sure I could have said it in a terse paragraph as a comment instead. This is not necessarily optimal in any way. I don't know much about other types of designs that might yield useful examples/constructions (maybe beating $n^2/24$), and I'm sure there are other approaches to the problem that don't involve designs.

Addendum / second answer: Here's another addition to the discussion that really ought to be another comment. The really nice answer by t3suji is pointing to an underlying structure that symmetric differences have that (regular) differences do not -- they give us an arithmetic that is just like $\mathbb{F}_2^n$. In the finite field context, what we want is a Sidon set. You can find in several sources (e.g. Tao-Vu exercise 4.5.8 or this paper) that $a_n\le 2^{n/2}$ (with $a_n$ as in t3suji's answer), which is close to the $2^{n/3}$ roughly given by t3suji's answer. But, unless I'm seriously misremembering things I read a few years ago (but can't seem to find anymore), there are Sidon sets that meet the bound $2^{n/2}$ bound give or take a constant, which translates into a $\sim 2^{n/4}$ bound for our problem after doing the same trick we all keep doing. I would wager this one might be best possible.