Revisions to Number of vectors so that no two subset sums are equal

added 122 characters in body

Source Link

edited Feb 25, 2014 at 3:47

37.7k
3
80
147

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, with 2 nonequivalentinequivalent solutions, example

10
11

$n=3$: best is 4, with 2 nonequivalentinequivalent solutions, example

$n=4$: best is 5, with 48 nonequivalentinequivalent solutions, example

$n=5$: best is 7, with 877 nonequivalentinequivalent solutions, example

$n=6$: best is 9, with 114227 nonequivalentinequivalent solutions, example

$n=7$: best is 12, with 118485 nonequivalentinequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page[combinatorial data page][1].

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 299927620 sets of size 19 and will findbut there are more. Here is one:

In a separate answer I prove an upper bound of 30 for $n=10$. However I will be quite surprised if even 20 is possible. [1]: http://cs.anu.edu.au/~bdm/data/dissociated.html

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, 2 nonequivalent solutions, example

10
11

$n=3$: best is 4, with 2 nonequivalent solutions, example

$n=4$: best is 5, with 48 nonequivalent solutions, example

$n=5$: best is 7, with 877 nonequivalent solutions, example

$n=6$: best is 9, with 114227 nonequivalent solutions, example

$n=7$: best is 12, with 118485 nonequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page.

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 2999 sets of size 19 and will find more. Here is one:

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, with 2 inequivalent solutions, example

10
11

$n=3$: best is 4, with 2 inequivalent solutions, example

$n=4$: best is 5, with 48 inequivalent solutions, example

$n=5$: best is 7, with 877 inequivalent solutions, example

$n=6$: best is 9, with 114227 inequivalent solutions, example

$n=7$: best is 12, with 118485 inequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my [combinatorial data page][1].

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 27620 sets of size 19 but there are more. Here is one:

In a separate answer I prove an upper bound of 30 for $n=10$. However I will be quite surprised if even 20 is possible. [1]: http://cs.anu.edu.au/~bdm/data/dissociated.html

added 1 characters in body

Source Link

edited Feb 23, 2014 at 23:43

Brendan McKay

37.7k
3
80
147

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, 2 nonequivalent solutions, example

10
11

$n=3$: best is 4, with 2 nonequivalent solutions, example

$n=4$: best is 5, with 48 nonequivalent solutions, example

$n=5$: best is 7, with 877 nonequivalent solutions, example

$n=6$: best is 9, with 114227 nonequivalent solutions, example

$n=7$: best is 12, with 118485 nonequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page.

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 1722999 sets of size 19 and will find more. Here is one:

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, 2 nonequivalent solutions, example

10
11

$n=3$: best is 4, with 2 nonequivalent solutions, example

$n=4$: best is 5, with 48 nonequivalent solutions, example

$n=5$: best is 7, with 877 nonequivalent solutions, example

$n=6$: best is 9, with 114227 nonequivalent solutions, example

$n=7$: best is 12, with 118485 nonequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page.

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 172 sets of size 19 and will find more. Here is one:

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, 2 nonequivalent solutions, example

10
11

$n=3$: best is 4, with 2 nonequivalent solutions, example

$n=4$: best is 5, with 48 nonequivalent solutions, example

$n=5$: best is 7, with 877 nonequivalent solutions, example

$n=6$: best is 9, with 114227 nonequivalent solutions, example

$n=7$: best is 12, with 118485 nonequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page.

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 2999 sets of size 19 and will find more. Here is one:

added 687 characters in body

Source Link

edited Feb 23, 2014 at 23:02

Brendan McKay

37.7k
3
80
147

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, 2 nonequivalent solutions, example

10
11

$n=3$: best is 4, with 2 nonequivalent solutions, example

$n=4$: best is 5, with 48 nonequivalent solutions, example

$n=5$: best is 7, with 877 nonequivalent solutions, example

$n=6$: best is 9, with 114227 nonequivalent solutions, example

$n=7$: best is 12, with 118485 nonequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page.

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 172 sets of size 19 and will find more. Here is one:

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, 2 nonequivalent solutions, example

10
11

$n=3$: best is 4, with 2 nonequivalent solutions, example

$n=4$: best is 5, with 48 nonequivalent solutions, example

$n=5$: best is 7, with 877 nonequivalent solutions, example

$n=6$: best is 9, with 114227 nonequivalent solutions, example

$n=7$: best is 12, with 118485 nonequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page.

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, 2 nonequivalent solutions, example

10
11

$n=3$: best is 4, with 2 nonequivalent solutions, example

$n=4$: best is 5, with 48 nonequivalent solutions, example

$n=5$: best is 7, with 877 nonequivalent solutions, example

$n=6$: best is 9, with 114227 nonequivalent solutions, example

$n=7$: best is 12, with 118485 nonequivalent solutions, example

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page.

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 172 sets of size 19 and will find more. Here is one:

added 159 characters in body

Source Link

edited Feb 18, 2014 at 6:54

Brendan McKay

37.7k
3
80
147

Loading

add more data

Source Link

edited Feb 18, 2014 at 2:14

Brendan McKay

37.7k
3
80
147

Loading

none on 13

Source Link

edited Feb 16, 2014 at 22:09

Brendan McKay

37.7k
3
80
147

Loading

added 225 characters in body

Source Link

edited Feb 16, 2014 at 2:17

Brendan McKay

37.7k
3
80
147

Loading

added 235 characters in body

Source Link

edited Feb 16, 2014 at 0:12

Brendan McKay

37.7k
3
80
147

Loading

Source Link

created Feb 15, 2014 at 13:45

Brendan McKay

37.7k
3
80
147

Loading

Stack Exchange Network

Return to Answer