This is a variant of the unsolved problem of $a^6+b^6+c^6≠d^6+e^6+f^6$, for distinct primes. Does it have any significance for Exact Three Cover?

Question

Suppose, I'm solving Exact 3 Cover, given a list with no duplicates $S$ of $3m$ whole numbers and a collection $C$ of subsets of $S$, each containing exactly three elements. The goal is to decide if there are $len(S)/3$ subsets that cover every element in $S$ one time.

$N$ is the $len(S)$

I'm going to use Subset Sum to solve Exact 3 Cover.

I reduce Exact Three Cover into Subset Sum by transforming $S$ into $N$ distinct primes raised to 6, and easily map out the collection of subsets in the same manner. I then get the sums of the transformed collection of subsets. And the sum of the transformed $S$ will be our target sum.

So now I have a transformed $S = {p_1^6, p_2^6, p_3^6...}$ into the first $N$ distinct primes raised to 6.

A collection of subsets would be represented as {$p_1^6, p_2^6, p_3^6$}, {$p_4^6,p_5^6,p_6^6$}....

Update: If 2 becomes an issue, we can just use the first N distinct odd primes instead.

Update: Does the unique factorization of $p_i^6$ also imply that $S$ has a unique sum thus preventing collisions? I've exhaustively tried combinations allowing repeated usage from $S$ to simulate collisions. I wanted to see if it were possible to get a sum to $S$ with repeated usage. Didn't find a counter-example this way either. If brute force won't practically find a counter-example, then we need to figure out something more clever. Perhaps this link to mathoverflow might help in constructing a counter example.

There are rules for combinations of size three to ensure distinctness.

• All combinations of size three must be sorted in ascending order.

• There will be no duplicate subsets.

• There will be no subsets that have elements not in $S$.

• There will be no subsets that have duplicate elements.

• This does not affect correctness, as it is either impossible or not necessary that a solution could use these subsets. We easily filter the input to get rid of these unnecessary subsets.

The conjecture is that no distinct subset that was transformed into primes raised to 6 could have duplicate sums. This is a variant of the unsolved problem of $a^6 + b^6 + c^6 ≠ d^6 + e^6 + f^6$ where variables are distinct primes.

In this case both sides of the equation is supposed to be distinct subsets of size three. Of course, we have to tweak it to encapsulate all combinations of size 3.

For example,

When a variable is shared between two distinct subsets.

$A^6 + b^6 + c^6 ≠ A^6 + e^6 + f^6$

$b^6 + c^6 ≠ e^6 + f^6$ is another open problem for distinct primes, it also implies $A^6 + b^6 + c^6 ≠ A^6 + e^6 + f^6$

When two variables are shared between two distinct subsets.

$A^6 + B^6 + c^6 ≠ A^6 + B^6 + f^6$.

For generality the position of shared variables could be at any location on either side of the equation.

Also the unique factorization of each $p^6$ seems to imply unique sums for all combinations of size 3.

Here's a link to my code for empirical analysis showing no duplicate sums

Let's say that conjecture is true, what about the sum of the transformed $S$? I asked this because we will be using the Subset Sum dynamic solution to solve Exact 3 Cover. Since there's no duplicate sums per the conjecture, then there should be no collisions resulting a false output when we use the Subset Sum algorithm.

The magnitude of the sum of the transformed S.

Let's denote the $i-th$ prime number as $p_i$ where $i = 1,2,....len(S)$. The sum of the transformed $S$ can be represented as $\sum_{i=1}^{len(S)} p_i^6$

Now to prove that the sum is polynomial, we need to show that the largest term in the sum grows polynomially with respect to $len(S)$.

If my understanding is correct (and I could be wrong) the $i-th$ prime number, $p_i$ is approximately $i*log(i)$ according to the prime number theorem.

Therefore, $p_i^6$ can be approximated as $(i*log(i))^6$.

Expanding the expression, I get:

$(i*log(i))^6 = i^6 * (log(i))^6$

Both $i^6$ and $(log(i)^6$ are polynomial functions. Therefore, the sum $\sum_{i=1}^{len(S)} p_i^6$ is a sum of polynomial terms, making it polynomial.

But if my understanding is correct seems to show that the magnitude of the sum of the transformed $S$ is polynomial in the size of $S$.

If we use the subset sum dynamic solution which is pseudo polynomial, it would be polynomial in the transformed size of $S$.

Has this conjecture already been shown to imply $P=NP$, or has it been debunked?

Where's the counter-example?

Answer 1

I think that you cannot guarantee an unique sum, but the numbers for a counterexample must be taken at "the end of the universe".

You can find primes $p_{i_j}$ and factors $k_j$ such that $\sum_{j=1}^N k_j p_{i_j}^6 = p_{i_{N+1}}^6$.

For example: $8^6 + 12^6 + 30^6 + 78^6 + 102^6 + 138^6 + 165^6 + 246^6 = 251^6$

we can "extract" a distinct prime from each one of the 6-th powers:

$8^6 = 4096 * 2^6,\;$ $12^6 = 4096 * 3^6,\;$ $30^6 = 46656 * 5^6,\;$ $78^6 = 46656 * 13^6,\;$ $102^6 = 17 46656 * 17^6,\;$ $138^6 = 46656 * 23^6,\;$ $165^6 = 11390625 * 11^6,\;$ $246^6 = 46656 * 41^6 $

so if you have $4096+1$ 3 elements subsets that contains a common $2^6$ (and the others are all distinct "new elements"), $4096+1$ 3 elements subsets that contains a common $3^6$ (and the others are all ditinct "new elements"), and so on ...

You get a collection of (overlapping) sets that represents the elements $2^6 , 3^6 , 5^6 , 13^6 , 17^6, 23^6, 11^6, 41^6$ and the "new" $251^6$, plus a very large set of unique (and non-overlapping) elements.

If the element $251^6$ is not included in any of the 3 element subsets (or included in a forced invalid overlapping chain of primes) you get a VALID YES INSTANCE of the Subeset Sum from a NO INSTANCE of the original 3XC problem.