<p>I think that you cannot guarantee an unique sum, but the numbers for a counterexample must be taken at &quot;the end of the universe&quot;.</p>
<p>You can find primes <span class="math-container">$p_{i_j}$</span> and factors <span class="math-container">$k_j$</span> such that <span class="math-container">$\sum_{j=1}^N k_j p_{i_j}^6 = p_{i_{N+1}}^6$</span>.</p>
<p>For example: <span class="math-container">$8^6 + 12^6 + 30^6 + 78^6 + 102^6 + 138^6 + 165^6 + 246^6 = 251^6$</span></p>
<p>we can &quot;extract&quot; a distinct prime from each one of the 6-th powers:</p>
<p><span class="math-container">$8^6 = 4096 * 2^6,\;$</span>
<span class="math-container">$12^6 = 4096 * 3^6,\;$</span>
<span class="math-container">$30^6 = 46656 * 5^6,\;$</span>
<span class="math-container">$78^6 = 46656 * 13^6,\;$</span>
<span class="math-container">$102^6 = 17 46656 * 17^6,\;$</span>
<span class="math-container">$138^6 = 46656 * 23^6,\;$</span>
<span class="math-container">$165^6 = 11390625 * 11^6,\;$</span>
<span class="math-container">$246^6 = 46656 * 41^6 $</span></p>
<p>so if you have <span class="math-container">$4096+1$</span> 3 elements subsets that contains a common <span class="math-container">$2^6$</span> (and the others are all distinct &quot;new elements&quot;), <span class="math-container">$4096+1$</span> 3 elements subsets that contains a common <span class="math-container">$3^6$</span> (and the others are all ditinct &quot;new elements&quot;), and so on ...</p>
<p>You get a collection of (overlapping) sets that represents the elements <span class="math-container">$2^6 
, 3^6 , 5^6 , 13^6 , 17^6, 23^6, 11^6, 41^6$</span> and the &quot;new&quot; <span class="math-container">$251^6$</span>, plus a very large set of unique (and non-overlapping) elements.</p>
<p>If the element <span class="math-container">$251^6$</span> 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.</p>

CC BY-SA 4.0
2024-04-12T01:02:25.620Z
You actually went through it and gave an example. Nice !
Tayfun Pay
CC BY-SA 4.0
2024-04-12T01:04:01.507Z
Its been a hurtin' for me. I'm impressed. Of course I will continue my research into seeing what larger exponents would do.
The T
CC BY-SA 4.0
2024-04-12T01:19:35.613Z
Just curious how large was S and C?
The T
CC BY-SA 4.0
2024-04-12T07:12:08.253Z
@TheT: $S$ contains at least 2*(4097+4097+46657+46657+1746657
+46657+11390627+46657)+8 distinct elements (each one mapped to a $p_i^6$) in order to build enough 3 element subsets that sum up to 251^6; plus a bunch of other elements to fill the gaps and make the total count divisible by 3 (7^6,19^6, 27^6, ..., 241^6, 251^6, 257^6) ... something like N=13230648 elements .
Marzio De Biasi
CC BY-SA 4.0
2024-04-12T07:18:41.743Z
@TheT: ... and don't give up! perhaps something interesting could come from the probabilities of getting an overlapping sequence?!?
Marzio De Biasi
CC BY-SA 4.0
2024-04-12T10:08:22.593Z
@MarzioDeBiasi So what about counterexamples significantly smaller or is it impossible for a counter example to be smaller than that?  Because then I can just raise the exponent to see if I could learn something about the numbers.
The T
CC BY-SA 4.0
2024-04-12T12:38:08.017Z
@TheT: I think it's hard to find a smaller counterexample (I just looked at the KNOWN 6-th power diophantine equations, and it is very small). And be aware to play with larger exponents, because number-theory is full of UNKNOWN/UNPROVED stuff even for "smaller" objects so you risk getting nowhere. Even for your actual question, it is unknown if you can represent a 3-element subset uniquely with the sum of 3 6-th prime powers without any collision (so even if there had been no counterexample to the entire reduction, you would have been stuck)
Marzio De Biasi
CC BY-SA 4.0
2024-04-12T00:37:33.830Z
2024-04-12T07:28:30.933Z
2024-04-12T07:28:30.933Z
Marzio De Biasi
<p>Suppose, I'm solving Exact 3 Cover, given a list with no duplicates <span class="math-container">$S$</span> of <span class="math-container">$3m$</span> whole numbers and a collection <span class="math-container">$C$</span> of subsets of <span class="math-container">$S$</span>, each containing exactly three elements. The goal is to decide if there are <span class="math-container">$len(S)/3$</span> subsets that cover every element in <span class="math-container">$S$</span> one time.</p>
<p><span class="math-container">$N$</span> is the <span class="math-container">$len(S)$</span></p>
<p>I'm going to use Subset Sum to solve Exact 3 Cover.</p>
<p>I reduce Exact Three Cover into Subset Sum by transforming <span class="math-container">$S$</span> into <span class="math-container">$N$</span> 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 <span class="math-container">$S$</span> will be our target sum.</p>
<p>So now I have a transformed <span class="math-container">$S = {p_1^6, p_2^6, p_3^6...}$</span> into the first <span class="math-container">$N$</span> distinct primes raised to 6.</p>
<p>A collection of subsets would be represented as {<span class="math-container">$p_1^6, p_2^6, p_3^6$</span>}, {<span class="math-container">$p_4^6,p_5^6,p_6^6$</span>}....</p>
<p><strong>Update:</strong> If 2 becomes an issue, we can just use the first N distinct odd primes instead.</p>
<p><strong>Update:</strong> Does the unique factorization of <span class="math-container">$p_i^6$</span> also imply that <span class="math-container">$S$</span> has a unique sum thus preventing collisions? I've exhaustively tried combinations allowing repeated usage from <span class="math-container">$S$</span> to simulate collisions. I wanted to see if it were possible to get a sum to <span class="math-container">$S$</span> 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. <a href="https://mathoverflow.net/questions/468737/could-i-possibly-exploit-distinct-odd-primes-raised-to-6-to-solve-exact-three-co?noredirect=1#comment1217200_468737">Perhaps this link to mathoverflow might help in constructing a counter example.</a></p>
<p>There are rules for combinations of size three to ensure distinctness.</p>
<ul>
<li><p>All  combinations of size three must be sorted in ascending order.</p>
</li>
<li><p>There will be no duplicate subsets.</p>
</li>
<li><p>There will be no subsets that have elements not in <span class="math-container">$S$</span>.</p>
</li>
<li><p>There will be no subsets that have duplicate elements.</p>
</li>
<li><p>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.</p>
</li>
</ul>
<p>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 <span class="math-container">$a^6 + b^6 + c^6 ≠ d^6 + e^6 + f^6$</span> where variables are distinct primes.</p>
<p>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.</p>
<p>For example,</p>
<p><strong>When a variable is shared between two distinct subsets.</strong></p>
<p><span class="math-container">$A^6 + b^6 + c^6 ≠ A^6 + e^6 + f^6$</span></p>
<p><span class="math-container">$b^6 + c^6  ≠ e^6 + f^6$</span> is another open problem for distinct primes,
it also implies <span class="math-container">$A^6 + b^6 + c^6  ≠ A^6 + e^6 + f^6$</span></p>
<p><strong>When two variables are shared between two distinct subsets.</strong></p>
<p><span class="math-container">$A^6 + B^6 + c^6 ≠ A^6 + B^6 + f^6$</span>.</p>
<p>For generality the position of shared variables could be at any location on either side of the equation.</p>
<p>Also the unique factorization of each <span class="math-container">$p^6$</span> seems to imply unique sums for all combinations of size 3.</p>
<p><a href="https://pastebin.com/edgQQNPd" rel="nofollow noreferrer">Here's a link to my code for empirical analysis showing no duplicate sums</a></p>
<p>Let's say that conjecture is true, what about the sum of the transformed <span class="math-container">$S$</span>?
I asked this because we will be using the Subset Sum dynamic solution to solve Exact 3 Cover. Since there's <strong>no duplicate sums per the conjecture</strong>, then there should be no collisions resulting a false output when we use the Subset Sum algorithm.</p>
<p>The magnitude of the sum of the transformed S.</p>
<p>Let's denote the <span class="math-container">$i-th$</span> prime number as <span class="math-container">$p_i$</span> where <span class="math-container">$i = 1,2,....len(S)$</span>. The sum of the transformed <span class="math-container">$S$</span> can be represented as <span class="math-container">$\sum_{i=1}^{len(S)} p_i^6$</span></p>
<p>Now to prove that the sum is polynomial, we need to show that the largest term in the sum grows polynomially with respect to <span class="math-container">$len(S)$</span>.</p>
<p>If my understanding is correct (and I could be wrong) the <span class="math-container">$i-th$</span> prime number, <span class="math-container">$p_i$</span> is approximately <span class="math-container">$i*log(i)$</span> according to the prime number theorem.</p>
<p>Therefore, <span class="math-container">$p_i^6$</span> can be approximated as <span class="math-container">$(i*log(i))^6$</span>.</p>
<p>Expanding the expression, I get:</p>
<p><span class="math-container">$(i*log(i))^6 = i^6 * (log(i))^6$</span></p>
<p>Both <span class="math-container">$i^6$</span> and <span class="math-container">$(log(i)^6$</span> are polynomial functions. Therefore, the sum <span class="math-container">$\sum_{i=1}^{len(S)} p_i^6$</span> is a sum of polynomial terms, making it polynomial.</p>
<p>But if my understanding is correct seems to show that the magnitude of the sum of the transformed <span class="math-container">$S$</span> is polynomial in the size of <span class="math-container">$S$</span>.</p>
<p>If we use the subset sum dynamic solution which is pseudo polynomial, it would be polynomial in the transformed size of <span class="math-container">$S$</span>.</p>
<p>Has this conjecture already been shown to imply <span class="math-container">$P=NP$</span>, or has it been debunked?</p>
<p>Where's the counter-example?</p>

CC BY-SA 4.0
2024-04-11T13:13:06.463Z
It is unclear (to me) how the proposed reduction from X3C to Subset Sum works. For example, given the simple (Yes) instance of X3C $S=\{1,2,3,4,5,6\}$ $C = \{\{1,2,3\},\{4,5,6\},\{2,3,4\}\}$; what are the numbers associated with each subset in $C$ and what is the total target sum wanted?
Marzio De Biasi
CC BY-SA 4.0
2024-04-11T16:20:14.567Z
... ok, now I got it: the target sum is $\sum_{i=1}^{|S|} p_i^6$; each subset $\{a_i, a_j, a_k\}$ in $C$ is represented simply with $p_i^6 + p_j^6 + p_k^6$ (and the reduction is polynomial-time).
Marzio De Biasi
CC BY-SA 4.0
2024-04-11T17:19:00.187Z
@MarzioDeBiasi I tried writing my reduction in python code, as I see you're programmer. If I don't have any bugs I hope this helps. Forgive me if the code is to long. https://pastebin.com/RxKViyXa     Edit: I forgot to output the target sum, but its defined as N in the code.
The T
CC BY-SA 4.0
2024-04-11T18:01:31.967Z
@MarzioDeBiasi In the linked pastebin get_the_sums should've been this https://pastebin.com/LivhbgEV . We need to see if duplicate sums are possible.
The T
CC BY-SA 4.0
2024-04-12T06:56:54.347Z
https://mathoverflow.net/q/468737/37212, https://math.stackexchange.com/q/4894190/14578
D.W.
<reductions><np-complete>
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?
The T
# 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?

(Asked by: username_0 on 2024-04-09)

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.](https://mathoverflow.net/questions/468737/could-i-possibly-exploit-distinct-odd-primes-raised-to-6-to-solve-exact-three-co?noredirect=1#comment1217200_468737)

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](https://pastebin.com/edgQQNPd)

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?

**Tags:** reductions, np-complete
> **Comments:**
> **username_1**: It is unclear (to me) how the proposed reduction from X3C to Subset Sum works. For example, given the simple (Yes) instance of X3C $S=\{1,2,3,4,5,6\}$ $C = \{\{1,2,3\},\{4,5,6\},\{2,3,4\}\}$; what are the numbers associated with each subset in $C$ and what is the total target sum wanted?  
> **username_1**: ... ok, now I got it: the target sum is $\sum_{i=1}^{|S|} p_i^6$; each subset $\{a_i, a_j, a_k\}$ in $C$ is represented simply with $p_i^6 + p_j^6 + p_k^6$ (and the reduction is polynomial-time).  
> **username_0**: @MarzioDeBiasi I tried writing my reduction in python code, as I see you're programmer. If I don't have any bugs I hope this helps. Forgive me if the code is to long. https://pastebin.com/RxKViyXa     Edit: I forgot to output the target sum, but its defined as N in the code.  
> **username_0**: @MarzioDeBiasi In the linked pastebin get_the_sums should've been this https://pastebin.com/LivhbgEV . We need to see if duplicate sums are possible.  
> **username_2**: https://mathoverflow.net/q/468737/37212, https://math.stackexchange.com/q/4894190/14578  

---

## 1 answers

### Answer by username_1 on 2024-04-12. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_3**: You actually went through it and gave an example. Nice !  
> **username_0**: Its been a hurtin' for me. I'm impressed. Of course I will continue my research into seeing what larger exponents would do.  
> **username_0**: Just curious how large was S and C?  
> **username_1**: @TheT: $S$ contains at least 2*(4097+4097+46657+46657+1746657 +46657+11390627+46657)+8 distinct elements (each one mapped to a $p_i^6$) in order to build enough 3 element subsets that sum up to 251^6; plus a bunch of other elements to fill the gaps and make the total count divisible by 3 (7^6,19^6, 27^6, ..., 241^6, 251^6, 257^6) ... something like N=13230648 elements .  
> **username_1**: @TheT: ... and don't give up! perhaps something interesting could come from the probabilities of getting an overlapping sequence?!?  
> **username_0**: @MarzioDeBiasi So what about counterexamples significantly smaller or is it impossible for a counter example to be smaller than that?  Because then I can just raise the exponent to see if I could learn something about the numbers.  
> **username_1**: @TheT: I think it's hard to find a smaller counterexample (I just looked at the KNOWN 6-th power diophantine equations, and it is very small). And be aware to play with larger exponents, because number-theory is full of UNKNOWN/UNPROVED stuff even for "smaller" objects so you risk getting nowhere. Even for your actual question, it is unknown if you can represent a 3-element subset uniquely with the sum of 3 6-th prime powers without any collision (so even if there had been no counterexample to the entire reduction, you would have been stuck)  

---

