Prove that the sets $s_i := \{1\leq j \leq m: (i-1)\odot j = 1\}$ form a $\dfrac{1024}{2047}$-good subset of $T_{2047}$ of size $2048$.

Question

Let $m$ be a positive integer, and let $T_m$ denote the set of all subsets of $\{1,\cdots, m\}$. Call a subset $S$ of $T$ $\delta$-good if for all $s_1, s_2\in S, s_1\neq s_2, |\Delta (s_1, s_2)| \ge \delta m,$ where $\Delta $ denotes the symmetric difference.

Define for two binary sequences $x=(x_1,\cdots, x_{11})_2, y = (y_1,\cdots, y_{11})_2, x\odot y := \sum x_i y_i \mod 2$. Let for $1\leq i\leq 2048,s_i := \{1\leq j \leq m: (i-1)\odot j = 1\}$

Question: Prove that the sets $s_i := \{1\leq j \leq m: (i-1)\odot j = 1\}$ form a $\dfrac{1024}{2047}$-good subset of $T_{2047}$ of size $2048$.

We just have to show that for any two distinct sets $ s_i\neq s_j, |\Delta (s_i,s_j)| \ge 1024.$ First note that for any two integers $x,y\leq 2047, x\circ y$ is precisely the parity of the number of 1's that x and y share. Now for two distinct sets $s_i\neq s_j, k \in s_i\backslash s_j \Leftrightarrow (i-1)\odot k = 1\wedge (j-1)\odot k = 0.$ So $k$ has an odd number of 1's in common with $i-1$ and an even number of 1's in common with $j-1$. Similarly, $k\in s_j\backslash s_i\Leftrightarrow (i-1)\odot k = 0\wedge (j-1)\odot k = 1.$ So k has an even number of 1's in common with i-1 and an odd number in common with j-1. Thus $k\in \Delta (s_i,s_j)$ iff the number of ones k shares with i - 1 is of opposite parity to the number of ones k shares with j - 1. Now it would be very convenient if there was some sort of bitwise operation or some other fast method of checking the latter condition.

Answer 1

This is just for the justification that $s_i$ work.

First, because I don't like dealing with $s_i = \{(i-1 ) \odot j=1\} $, and much rather deal with $s_i = \{ i \odot j = 1\}$, I'm going to relabel the sets to $ s_0, s_1, \ldots s_{2047}$.

• Show that $ |s_i| = 1024$.
• Show that $s_i \Delta s_j = s_{i \oplus j} $, where $i\oplus j$ refers to taking XOR bitwise.
  • You came close to this in the writeup. For example, for $ k \in s_i \backslash s_j$, the parity that $k$ has 1s in common with $i $ and $j$ is distinct. This implies that the parity that $k$ 1's in common with where $i$ and $j$ differ, is also distinct.
• Hence, $ |s_i \Delta s_j | = 1024 \geq 1024$ as required.