# How many elements with a hamming distance of 3 or less?

[This is a complete rewrite which makes some of the comments redundant or irrelevant.]

Take a set of $50$ elements. How many subsets of size $5$ are needed so that every subset of size $5$ will intersect at least one of these in at least $2$ points?

This collection of subsets is known as a lottery wheel or a lotto design. $L(v,k,p,t)$ is the minimum number of subsets of a $v$ element set so that each subset has size $k$ with the property that every $p$ element subset intersects at least one $k$-subset in at least $t$ points. If you select $5$ out of $50$ numbers in a lottery which pays a prize for getting at least $2$ numbers right, then you can ensure getting a prize if you buy a particular collection of $L(50,5,5,2)$ tickets. The question is to find $L(50,5,5,2)$.

• Could you explain your definition of $d_h$ a bit more? (By the way, that formula defining $S$ is horrendous! Words really are better for these things.) – James Cranch Jun 6 '11 at 13:58
• This sounds like lottery wheels or lottery designs. I suggest a web search. Gerhard "Ask Me About System Design" Paseman, 2011.06.06 – Gerhard Paseman Jun 6 '11 at 18:53
• @chous: you have not really defined $S_3$ uniquely. I think what you're really saying is that you want some set $T$ such that for every $s \in S$ there is some $t \in T$ with $d_h(s,t) \le 3$. There are lots of such sets, for example $S$ itself. But perhaps what you want is one with minimum cardinality: you're talking about a "minimal cover problem" in a graph $G$ consisting of the elements of $S$, with edges corresponding to pairs with Hamming distance $\le 3$. – Robert Israel Jun 7 '11 at 0:54
• Hamming distance works better on sequences than on sets. Although we could phrase your distance in terms of the symmetric distance of two sets, I think it easier to say "For any 5-set t, I want there to be at least one of my 5-sets s in S such that s intersect t has at least two elements. Further, I want S chosen so that S has as few 5-sets in it as can be managed." The La Jolla Covering Repository answers this sort of question (if I read it right). Do a web search and check it out if you agree. Gerhard "Donates Regularly To Mega Millions" Paseman, 2011.06.06 – Gerhard Paseman Jun 7 '11 at 1:44
• You are asking for a wheel with parameters $(50,5,2)$. A covering design is different, which is unfortunate because there is a nice searchable database of covering designs, the La Jolla Covering Repository which Gerhard Paseman mentions. Most of the web hits when you search for lottery wheels are trying to sell junk to lottery players. – Douglas Zare Jun 7 '11 at 8:29

You are not using the positions at all. You have 50 points. $S$ is the set of all $\binom{50}{5}=2118760$ selections of 5 points. You want a subset $B \subset S$ such that any $s \in S$ intersects at least one $b \in B$ in at least 2 points. That is an interesting problem and does not immediately strike me as familiar. Call a member of $B$ a block. A given block intersects $152026$ members of $S$ in 2 or more points. This gives a lower bound of $14$ for the possible size of $B$. Of course this a weak bound since two disjoint blocks determine $200$ members of $S$ intersecting one in 2 points and the other in 3 and another $4000$ intersecting each in 2 points. If my calculations are correct, that raises the lower bound to at least $19$ blocks. I doubt that $20$ would suffice.

So far my record is 44 blocks.

Let me digress for some terminology (which I'll try to keep fairly standard). a design is a pair $D=(V,B)$ where $V$ is a set of $v$ vertices and a $B$ is a collection of subsets called blocks There are various names for designs which satisfy additional conditions. Two are

Every pair of points is in exactly one common block. (Then $D$ is called a linear space)

Every pair of points is in at least one common block and every block has the same number $k$ of points. (Then $D$ is called a $(v,k,2)$-covering design and the La Jolla Repository has information about these.)

When both conditions hold, $D$ is called a Steiner System $S(2,k,v).$ Many that one encounters arise from algebraic constructions. This is perhaps due to the Streetlight effect.

I'll coin the term super-linear space for a design such that every pair of points from $V$ occur in at least one common block but the blocks may have various sizes (since I don't know a standard name. It turns out that this might be called a lottery wheel although that term is not very specific)

You have $50$ points and do not require that every pair of points is in a block but do wish that from every 5 points (element of $S$), at least one pair is in at least one block. You also want all blocks to have $5$ points. I'll find it convenient to only require that each block have at most 5 points, then one can arbitrarily enlarge blocks to size 5.

All my constructions have this form: Split the points into 4 groups (or 2 or 3) and for each group take a super-linear space with no block having more than 6 points. Then any element of $S$ has two points in the same group and those two points are in a common block. Perhaps one can do better without this restriction. I include a few other possibilities in case it inspires anyone to get a better result.

44* blocks. Split into 4 groups of size 21,21,4 and 4. For each of the large groups take the 21 lines of a projective plane of order 4 and let the two small groups be 4 point blocks. Now any set in $S$ has at least two points in a common group and those two pints determine a unique block.

60 blocks: split the points into two sets of 25 and use the 30 lines of an affine plane of order 5 on each. This is overkill because any 3 element set has two points in some block. Perhaps there is a way to cull out some of the lines.

Under 52 blocks If the points are partitioned into 3 groups of 13 and one of 11 (with two fake points added in) then (for each group) the lines of a projective plane of order 3 were taken as blocks this would give a solution with 52 blocks of size 4. Delete $X,Y$ to improve this to 45 of size 4 and 6 of size 3 and one of size two. Now tack the block of size 2 onto a block of size 3 to get $51$ blocks (one of size 5). (If $X,Y$ are in different groups it might be better, I haven't checked.) One can also get rid of at least 3 more blocks as follows: take a block abcd, delete it and add b as a fifth point to a block containing c and another containing c, add c as a fifth point to two blocks containing d and a and add d as a fifth point to two blocks containing a and b.

• Thanks a lot! How would you recommend to build the projective 3 space of order 4? I think I'm currently not ready for this task :(. – chous Jun 7 '11 at 12:18
• Aaron Meyerowitz's construction for $42$ blocks used $F_3$ rather than $F_4$, which should make it easier. The construction is just like that of $\mathbb{RP}^3$ so that the points are lines passing through the origin in $\mathbb{R}^4$ and the lines of $\mathbb{P}^3$ correspond to (two-dimensional) planes passing through the origin. $\mathbb{P}^3(F_4)$ has $(4^4-1)/(4-1)=85$ points, though. – Douglas Zare Jun 7 '11 at 17:53
• $\mathbb{P}^3(F_3)$ has ${40 \choose 2}/{4 \choose 2} = 130$ lines, not $40$, so the construction for $42$ blocks actually uses $132$ blocks. It was a little too good to be true since it would mean any quadruple would intersect a block in $2$ points, and it would be easy to use the $5$th points to make a line redundant. – Douglas Zare Jun 7 '11 at 18:40

Here is a construction of size $38$. Call the points cards and divide the deck into $4$ suits, so that $2$ suits have ranks $1,...,13$ and $2$ suits have ranks $1,...,12$. Every hand of $5$ cards must have at least $2$ cards in some suit. So, if we cover all possible pairs in each suit, the result will be a wheel.

The La Jolla Covering Repository says that $C(12,5,2)=9$ so we can cover all pairs within the short suits with $9$ hands each:

1  2  4  7  9
1  3  4  6 12
1  3  7 10 11
1  5  6  8 12
2  3  5  7  8
2  6 10 11 12
3  6  7  9 12
4  5  8 10 11
5  8  9 10 11


Similarly, it says $C(13,5,2) \le 10$ so we can cover all pairs within the long suits with $10$ hands each:

1  2  3  4  5
1  6  7  8  9
1 10 11 12 13
2  3  6  7 10
2  3  8  9 11
4  5  6  7 11
4  5  8  9 10
2  3  4 12 13
5  6  7 12 13
1  8  9 12 13


The total is $38$ hands which intersect each hand of $5$ cards in at least $2$ cards. So, $L(50,5,5,2) \le 38$.

Edit: The best this method can do with the coverings known in the La Jolla Repository is $37$. That can be done by splitting a $50$ card deck into suits of sizes $(17, 11, 11, 11),$ $(13,13,13,11)$, or $(15, 13, 11, 11)$.

$C(13,5,2) \le 10$ as shown above.

• Thanks (truly!) for clarifying the question and making my LJCR comment less useful (since a covering design was not wanted) and also more useful (by showing how two covering designs could help). Gerhard "Likes To Feel Really Useful" Paseman, 2011.06.07 – Gerhard Paseman Jun 7 '11 at 23:47
• Thanks! I wish I could mark more than one answers. Searching in the Internet I found a solution with 36 tuples, and I'll try to find more using your suggestions, but I'm not discarding using a "branch and bound" algorithm. – chous Jun 8 '11 at 19:45
• @Douglas Zare: Thanks for rewriting the question. It's much clearer now. – chous Jun 8 '11 at 19:50
• Please post at least a link to the wheel of size $36$, since it must have been constructed using a different method. It's ok to answer your own question. – Douglas Zare Jun 8 '11 at 20:01
• This 36 block solution is nice. It is actually close to one of the 37 block solutions by @Douglas. In the solution with suits of size 11,11,11,17 and covering designs of sizes 7,7,7,16, each covering design has a block which can be reduced to 3 cards. Take the 3 card blocks abc def ghi jkl and replace them by abcjk defjl ghikl. In fact one of the pairs from jkl ( in the 17 card suit) has a pair already covered so one could leave one of the hands with three cards. – Aaron Meyerowitz Jun 10 '11 at 5:38