A combinatorial problem
 

My knowledge of combinatorics is not good enough to solve the following problem. Can anyone help?

I want to find sets of 12-bit integers with the constraint that for every x_i and x_j in the set with i != j, weight(x_i EXOR x_j) >= c where c is a specified parameter. The function weight(x) is defined as the number of set bits in x.

For instance, this set of 15 integers satisfies the constraint for c=6:

{ 0x467, 0xDAE, 0xEDA, 0xB43, 0x3F0,
0xB1C, 0x879, 0x611, 0x19B, 0xAB7,
0xDD5, 0x2CD, 0x880, 0x22A, 0x548}

and this set of 21 satisfies the constraint for c=5:

{ 0xF7D, 0x473, 0x585, 0x3EB, 0x22E, 0xADA, 0xDE0,
0x906, 0x1FC, 0x310, 0x6D4, 0x01D, 0xF43, 0xA21,
0xFB6, 0x93B, 0xE8F, 0x448, 0x8E7, 0x6B9, 0x59A}.

I've found a set of 64 for c=4.


The problem is: what is the maximum size of an admissible set as a function of c and how can a set of maximum size be constructed?


Paul

BTW, the sets given above are [i]not[/i] optimal.

[QUOTE=xilman;201899]My knowledge of combinatorics is not good enough to solve the following problem. Can anyone help?

I want to find sets of 12-bit integers with the constraint that for every x_i and x_j in the set with i != j, weight(x_i EXOR x_j) >= c where c is a specified parameter. The function weight(x) is defined as the number of set bits in x.

For instance, this set of 15 integers satisfies the constraint for c=6:

{ 0x467, 0xDAE, 0xEDA, 0xB43, 0x3F0,
0xB1C, 0x879, 0x611, 0x19B, 0xAB7,
0xDD5, 0x2CD, 0x880, 0x22A, 0x548}

and this set of 21 satisfies the constraint for c=5:

{ 0xF7D, 0x473, 0x585, 0x3EB, 0x22E, 0xADA, 0xDE0,
0x906, 0x1FC, 0x310, 0x6D4, 0x01D, 0xF43, 0xA21,
0xFB6, 0x93B, 0xE8F, 0x448, 0x8E7, 0x6B9, 0x59A}.

I've found a set of 64 for c=4.


The problem is: what is the maximum size of an admissible set as a function of c and how can a set of maximum size be constructed?


Paul

BTW, the sets given above are [i]not[/i] optimal.[/QUOTE]

This is a variation of the "Postage Stamp" problem. See Richard Guy's
book on "Unsolved Problems in Number Theory".

Constructing such sets is a theoretically hard problem.

The literature on error correcting codes may have the solutions tabulated. In that language each of your integers is a code word, and you are specifying the minimum distance between code words. Distance c=6 could correct triple errors, distance c=5 could detect triple errors and correct double errors.

Does this set of 128 work for c=4?
[CODE]0x000
0x00F
0x033
0x03C
0x055
0x05A
0x066
0x069
0x096
0x099
0x0A5
0x0AA
0x0C3
0x0CC
0x0F0
0x0FF
0x303
0x30C
0x330
0x33F
0x356
0x359
0x365
0x36A
0x395
0x39A
0x3A6
0x3A9
0x3C0
0x3CF
0x3F3
0x3FC
0x505
0x50A
0x536
0x539
0x550
0x55F
0x563
0x56C
0x593
0x59C
0x5A0
0x5AF
0x5C6
0x5C9
0x5F5
0x5FA
0x606
0x609
0x635
0x63A
0x653
0x65C
0x660
0x66F
0x690
0x69F
0x6A3
0x6AC
0x6C5
0x6CA
0x6F6
0x6F9
0x906
0x909
0x935
0x93A
0x953
0x95C
0x960
0x96F
0x990
0x99F
0x9A3
0x9AC
0x9C5
0x9CA
0x9F6
0x9F9
0xA05
0xA0A
0xA36
0xA39
0xA50
0xA5F
0xA63
0xA6C
0xA93
0xA9C
0xAA0
0xAAF
0xAC6
0xAC9
0xAF5
0xAFA
0xC03
0xC0C
0xC30
0xC3F
0xC56
0xC59
0xC65
0xC6A
0xC95
0xC9A
0xCA6
0xCA9
0xCC0
0xCCF
0xCF3
0xCFC
0xF00
0xF0F
0xF33
0xF3C
0xF55
0xF5A
0xF66
0xF69
0xF96
0xF99
0xFA5
0xFAA
0xFC3
0xFCC
0xFF0
0xFFF
[/CODE]

And this set of 16 for c=6:
[CODE]0x000
0x0FF
0x356
0x3A9
0x563
0x59C
0x635
0x6CA
0x93A
0x9C5
0xA6C
0xA93
0xC59
0xCA6
0xF0F
0xFF0
[/CODE]

Neither of them are "proven" optimal

[QUOTE=xilman;201899]My knowledge of combinatorics is not good enough to solve the following problem. Can anyone help?

I want to find sets of 12-bit integers with the constraint that for every x_i and x_j in the set with i != j, weight(x_i EXOR x_j) >= c where c is a specified parameter. The function weight(x) is defined as the number of set bits in x.

For instance, this set of 15 integers satisfies the constraint for c=6:

{ 0x467, 0xDAE, 0xEDA, 0xB43, 0x3F0,
0xB1C, 0x879, 0x611, 0x19B, 0xAB7,
0xDD5, 0x2CD, 0x880, 0x22A, 0x548}

and this set of 21 satisfies the constraint for c=5:

{ 0xF7D, 0x473, 0x585, 0x3EB, 0x22E, 0xADA, 0xDE0,
0x906, 0x1FC, 0x310, 0x6D4, 0x01D, 0xF43, 0xA21,
0xFB6, 0x93B, 0xE8F, 0x448, 0x8E7, 0x6B9, 0x59A}.

I've found a set of 64 for c=4.


The problem is: what is the maximum size of an admissible set as a function of c and how can a set of maximum size be constructed?


Paul

BTW, the sets given above are [i]not[/i] optimal.[/QUOTE]

How about an approach like this to find a set:
find the weights of all combinations x_i, x_j (which is 2048*4095 combinations for 12 bits). Then find all the pairs with weight >= c, and find the cliques in this set.

Chris

[url]http://www.win.tue.nl/~aeb/codes/binary-1.html[/url]

[QUOTE=axn;201919]And this set of 16 for c=6:
[CODE]0x000
0x0FF
0x356
0x3A9
0x563
0x59C
0x635
0x6CA
0x93A
0x9C5
0xA6C
0xA93
0xC59
0xCA6
0xF0F
0xFF0
[/CODE]

Neither of them are "proven" optimal[/QUOTE]Thanks. The second is certainly not optimal, as shown by this set of 19 with weight 6:

{0x000, 0x5C3, 0x70E, 0x26B,
0xD94, 0xFFF, 0x3E4, 0x6D8,
0x476, 0x927, 0x95A, 0xC4D,
0xA3C, 0x8F1, 0xCAA, 0xB89,
0x09F, 0xE13, 0x539}

Curiously enough, my current best set for weight 5 has only 23 members. Surely it must be possible to do much better than that!

My algorithm is very simple-minded: start with x_0 equal to zero and then randomly select integers which meet the weight criterion for all previously selected values. When a preset total of calls to random() have been made, start again. Weights of (14, 20, 55) are very easy to find. Extending those limits becomes ever harder. I've spent perhaps 4 cpu-hours on a MacBook Pro to find the best so far. I won't spend much more before giving up and moving to a better algorithm (or just giving up).

I'm well aware that back-tracking is a better systematic approach. I've just not yet got around to implementing it.

Paul

A set should remain valid or invalid if you permute the bit indices, so you could start with a set containing 0 and 0...01...1[SUB]b[/SUB], where the latter has at least [I]c[/I] 1's.

Alex

for c=5, greedy algorithm yielded 25
[CODE]0
31
227
374
440
461
620
693
730
1145
1198
1236
1795
1820
2016
2047
2341
2378
2451
2603
2641
2694
3122
3143
3209[/CODE]

EDIT:- 26
[code]0
31
231
377
698
803
846
981
1138
1244
1427
1453
1589
1739
1816
2016
2156
2225
2358
2498
2643
2953
3115
3397
3718
4095
[/code]

[QUOTE=akruppa;201939]at least [I]c[/I] 1's.[/QUOTE]

This can be changed to "exactly c 1's." (using the assertion that, in a c-optimal solution, there will be at least one pair whose weight is exactly c. if such a pair doesn't exist, then a c-optimal solution will also be a c+1 optimal solution)