Here we collect some elementary observations on zero sum problems using symbolic calculators. This post is not complete. We simply want to demonstrate how to use polynomials in the style of generating functions to compute zero sums. [-JHM]
Symbolic Solutions to Zero Sum Problems
The zero subset sum decision problem is this:
Given a generic subset $S\subset \bf{Z}$ decide whether there exists a finite subset $S' \subset S$ which sums to zero.
The trouble here is always sampling over the powerset $2^S$ of all subsets of $S$. It's a very large set! Is there a categorical approach to enumerating the powerset? Here enters symbolic algebra, and a simple idea, that the powerset is essentially polynomial algebras.
Given a finite subset $S \subset \mathbf{Z}$, we formally define $$p=p_S(x)=\sum_{s\in S} x^s.$$ Evidently $p_S \in \mathbf{Z}[x, x^{-1}]$ belongs to the ring of Laurent polynomials, and is finitely supported since $\#(S) < +\infty$.
_A trivial observation: the coefficient of the degree zero term $x^0=1$ in the powers $p^k$ of $p=p_S$ for $k=1,2,\ldots, N$ represent solutions to zero sum problems, where $N=\#(S)$._
Remark. There is a distinction between zero sums and zero subset sums. If $S$ has cardinality $\#(S)=N$, then we allow any element $s\in S$ to be used at most $N$ times in the polynomial formulation of the zero sum problem. This is in contrast to the zero subset sum problem, where an element $s\in S$ can occur at most once.
For example $S=\{-2, 1, 3\}$ does not have any strict zero subset sums. However the constant coefficient in $q:=p^3=(x^{-2}+x+x^3)^3$ is nonzero because $-2+1+1=0$. So when we use polynomials to find zero sums, we must slightly expand the statement of the zero subset sum problem to allow for small multiplicity. A priori this small multiplicity is at most the cardinality of the set $N=\#(S)$, and we are supposing (yet to be proved) their computational equivalence.
In the zero subset sum problem, we have nothing except brute-force search over the subsets. There are no shortcuts or hidden information to accelerate the procedure.
This same problem arises with the polynomials. For we begin with an initial set $S$ with Laurent polynomial $p=p_S$. However we need to evaluate the coefficients of powers $q=p^k$ of this polynomial. But the real issue is that the powers of $p$ are not readily computed a priori. We cannot decide whether the constant coefficient is zero or not zero simply from the definition of $q=p^k$. This can only be decided a posteriori after explicit computation.
As obvious as this last sentence sounds, it's somewhat an open problem for most "logical mathematicians".
Question: Are there any analytical tricks for finding the coefficients of $q=p^k$ ? We know none, except Cauchy Residue formula, but it's not clear this is useful in our case...
from sympy import symbols, expand
# the indeterminate x.
x = symbols('x')
# formal Laurent polynomial defined by the subset S.
def poly(S):
return sum([x**k for k in S])
# returns the constant coefficient for small powers of p=poly(S):
def cc(S):
p=poly(S); N = len(S); output=[];
for j in range(N):
q=expand(p**(j+1))
output+= [q.coeff(x,0)]
#print("The constant coefficients of the small powers of p(S) are:")
return output
# returns Boolean True or False depending on whether there exists zero sum in S.
def existsZeroSum(S):
val = False;
if sum(cc(S))>0:
val = True
else:
pass
return val
import random
for j in range(6):
randomS = [random.randint(-200, 200) for j in range(6)];
print("Random S =", randomS, "has a zero subset sum:", existsZeroSum(randomS), "\n")
It's interesting to remark how the above algorithm loses information, i.e. it solves a decision problem, but does not immediately produce the actual solutions to the zero sum problem. When existsZeroSum returns True, it would be useful to also have the specific subset printed . This is work in progress.
To Do List:
- Interpret Meet-In-The-Middle for polynomial form of zero sum problem.
- What is application of Cauchy-Laurent residue formulas for evaluating coefficients?
- Prove or Disprove computational equivalence of discrete and polynomial subset sum problem.
- When existsZeroSum($S$)=True, return explicit zero sum $S'$.
Zero Sums with Small Coefficients: Computationally Equivalent?
Given a subset $S\subset \bf{Z}$ we are looking for coefficients $\epsilon$ satisfying $$\sum_{s\in S} \epsilon(s).s=0$$
In the classical discrete zero subset sum problem, the coefficients $\epsilon$ satisfy $\epsilon \in \{0, 1\}$.
In the polynomial form of the zero sum problem, the coefficients $\epsilon$ satisfy $\epsilon\in \{0,1,2,\ldots, \#(S)\}$.
Linear algebra and the linear dependance relations implies there exists infinitly many solutions to zero sum equation with coefficients satisfying $\epsilon \in \bf{N}_{\geq 0}$ and $\epsilon \in \bf{Z}$.
It's interesting to contrast the computational complexity of the zero sum equation in each case.
In our discussions we are effectively assuming a positive answer to the following question, although we must admit that we do not yet have a rigorous proof.
Question: Does the discrete zero subset sum problem have the same computational complexity as the "polynomial form" of the zero subset problem?
Again the difference between the two problems is that we allow coefficients with small multiplicity, namely $\epsilon\in \{0,1,\ldots, \#(S)\}$.