{"id":"48ef2390-e83f-49b3-b77d-6d4f684b0a9a","arxiv_id":"2412.04967","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Two deterministic algorithms are proposed for the (n,k)-complete hidden subset sum problem, including a symmetric-polynomial method with complexity O(sum p(u,<=k)^3 + binom(n,k)n) under non-singularity conditions.","lead":"The paper gives two deterministic algorithms for recovering a hidden list of n numbers from all of its k-element subset sums. One prunes brute-force search using ordering; the other builds a polynomial from symmetric function computations and recovers the numbers as its roots.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2 as printed has inverted break/failure conditions, making it non-executable even on the simplest instances.","rationale":"The reader's conditional verdict is appropriate, but the most load-bearing defect is more concrete than the exact-arithmetic limitation: the printed Algorithm 2 is internally inconsistent and cannot be executed as specified. In line 13 the break condition is inverted, and in line 3 the failure condition is inverted, so the algorithm either zeroes the first row of M or returns failure precisely when Theorem 2's hypothesis holds. The mathematical idea behind the algorithm is credible; the determinant-to-Moser-polynomial identity checks out on small examples and the power-sum reconstruction via Matrix (1) is coherent. However, because the theorem states that Algorithm 2 solves the problem, the pseudocode must be corrected before the claim is verifiable. The exact-arithmetic issue raised by the reader is also real and should be addressed by specifying the computational model: root-finding of an arbitrary real polynomial is not a finite unit-cost exact operation in the BSS model, and the cited O(n^3) companion-matrix method is approximate. Thus the paper needs (1) correction of the pseudocode and (2) an explicit statement of the real-computation model under which the algorithm is deterministic and exact. These are fixable, so the verdict remains conditional.","tokens_in":17829,"tokens_out":13915,"duration_ms":140565,"concrete_test":"Trace Algorithm 2 literally on the instance n=3, k=2, X_{3,2} = {3,4,5} (the 2-sums of X={1,2,3}). At u=1, L=[(1)], n(L)=1, n(L[1])=1, and since k=2 > 1, line 13 breaks before setting M(1,1), so M is the zero 1x1 matrix and line 27 tries to compute M^{-1}, which does not exist. This shows the algorithm as written cannot succeed on any instance with k ≥ 2. Applying the two one-character fixes (swap the comparison in line 13 and add '== 0' in line 3) makes the trace proceed and recover the roots.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 asserts Algorithm 2 deterministically recovers the hidden multiset. The pseudocode in Section 4.4 contradicts this. Line 13 reads 'if k > n(L[j]) then break', but L[1] = (u) has length 1 and k ≥ 2, so the loop breaks immediately and the first row of M stays all zeros, rendering M singular. Line 3 reads 'if [Moser polynomial expression] then return failure', but in standard pseudocode an if-condition is true when the expression is nonzero, so the algorithm returns failure exactly when the determinant condition required by Theorem 2 is satisfied. The surrounding prose in §4.2.3 makes clear the intended comparisons are 'n(L[j]) > k' and 'expression == 0', so these are likely typos; however, as printed the algorithm cannot be run, and the proof of Theorem 2 does not establish the stated result without those fixes. Additionally, the root-finding step (Algorithm 2, line 32) is not a finite exact operation over R in the standard BSS model; the cited O(n^3) method is numerical, so the exact deterministic recovery guarantee requires an explicit real-computation model or oracle.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the (n,k)-complete Hidden Subset Sum Problem over the reals and proposes two deterministic algorithms. Algorithm 1 is an optimized brute-force search exploiting ordering relations among subset sums. Algorithm 2 is the main contribution: it computes power sums of the hidden multiset X from power sums of the multiset of all k-subset sums through a sequence of linear systems (Matrix (1)), derives the determinant of these systems as a Moser-type polynomial, uses Newton identities to obtain elementary symmetric polynomials, and then recovers X as the roots of the polynomial constructed via Vieta's formulas. The claimed complexity is O(sum_{u=1}^n p(u,<=k)^3 + C(n,k)n). The paper also contains a theorem on permutation-symmetric subsets of X_{n,k} and a discussion of homogeneous symmetric polynomial rings.","tokens_in":18012,"tokens_out":13469,"duration_ms":144669,"significance":"The algebraic core of the paper is attractive and largely self-contained: the recursive extraction of power sums from subset sums is a natural application of symmetric function theory, the determinant formula is identified with the classical Moser polynomials, and the algorithm has no fitted parameters or circular normalizations. If Theorem 2 is made fully rigorous under a well-defined real computation model, the result would be a genuinely deterministic algebraic recovery method whose complexity is substantially better than exhaustive search for small k and moderate n. The discussion of when a basis of the homogeneous symmetric polynomial ring can be constructed from the subset-sum power sums S_u is also of independent interest. However, as printed, the central algorithmic claim is undermined by concrete pseudocode errors and by the lack of an exact model for the root-finding step.","major_comments":[{"comment":"The pseudocode contradicts Theorem 2. Line 13 reads \"if k > n(L[j]) then break\", but L[1] = (u) has length 1 and k >= 2, so the loop over j breaks immediately and the first row of M remains all zeros, making M singular on every input. The surrounding text and the matrix formula show that the intended condition is the opposite, namely n(L[j]) > k (or no break at all, since L already contains only partitions into at most k parts). Line 3 reads \"if sum ... then return failure\", which in standard pseudocode returns failure exactly when the determinant is nonzero, i.e. exactly when Theorem 2 guarantees recovery; the intended condition is \"if sum ... == 0\". These two errors make Algorithm 2 non-executable as printed and mean the current proof of Theorem 2 does not establish the stated deterministic recovery claim.","section":"§4.4, Algorithm 2"},{"comment":"The exact deterministic guarantee is not supported for the root-finding step. The instruction \"Find the n roots of the polynomial\" is not a finite exact operation in the standard BSS model over R, and the cited O(n^3) method based on companion-matrix eigenvalues is numerical. To substantiate Theorem 2 as stated, the paper needs to specify the real computation model, for example by treating roots as an oracle and counting that oracle as a unit-cost operation, or by giving an exact real-algebraic root isolation procedure with an appropriate complexity bound and error analysis. As written, the claimed deterministic recovery and the stated O(n^3) term for root finding are not justified.","section":"§4.4, line 32 and Theorem 2"},{"comment":"The proof of the determinant formula is too compressed at the point where the null vector c is related to the cofactors d_{i,j}. After Equation (2), the statement \"Since d_{1,1}=1=c_{1,1}, it follows that d_{i,j}=c_i\" needs the explicit chain: if B is the submatrix of Matrix (1) obtained by deleting the first row, then Bc=0 with c_1=1 gives B'(c_2,...,c_m) = -b_1, where B' is B with its first column b_1 removed; Lemma 2 then identifies (c_2,...,c_m) with the ratios of first-row cofactors A_{1j}/A_{11}. This link is not stated, and the current text jumps from a null-space computation to the cofactor expansion. Because the determinant formula is the invertibility criterion on which Theorem 2 rests, the proof should be expanded and the roles of c, b_1, and B' made explicit.","section":"§4.3, proof of Theorem 3"}],"minor_comments":[{"comment":"The condition \"if n|(k-1)!kn\" is ambiguous; it should state explicitly whether the exponent is n-1 or n, e.g. \"if n divides (k-1)! k^{n-1}\".","section":"§4.4, line 1"},{"comment":"\"Morse polynomial\" should be \"Moser polynomial\".","section":"Remark 2"},{"comment":"The answer to Question 1 is given as \"No with high probability!\"; this informal phrasing should be replaced by a precise conjecture or by a theorem with a proof, since the surrounding discussion is otherwise rigorous in tone.","section":"§4.6"},{"comment":"The sentence \"no closed-form expression for the partition function is known\" is inaccurate: exact formulas are known (for instance, the Hardy-Ramanujan-Rademacher series). The intended statement is presumably that no simple polynomial-type closed form exists.","section":"§4.4, bottom paragraph"},{"comment":"The counter-update logic in lines 23-36 is intricate and would benefit from a short invariant or example, because as presented it is hard to verify that all index combinations are generated exactly once.","section":"§3, Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The skeptical concern about Algorithm 2 lands: the two inverted conditions in the pseudocode are genuine and block the paper in its current form. The underlying mathematical construction appears sound and the fixes are local, so I do not recommend rejection. The other load-bearing issue is the exact-real model for root finding; the authors need to state a model or oracle explicitly. The determinant proof in Theorem 3 is likely correct but should be rewritten with the missing cofactor steps. I would also suggest that the authors verify the line 1 divisibility condition after fixing the exponent typo."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nPunchline: the algebraic core is mostly right, but Algorithm 2 as printed is broken—the break and failure conditions are inverted, so the algorithm would exit on the first partition and never solve anything. The surrounding text and math show the intended comparisons, so these look like typos, but they need fixing before anyone can use the paper.\n\nWhat actually works: the paper gives a deterministic symmetric-polynomial route to (n,k)-complete HSSP, with an explicit complexity bound O(Σ p(u,≤k)^3 + C(n,k)n), and a clean determinant identity: the determinant of Matrix (1) equals the Moser polynomial Σ (-1)^{i-1}(i-1)!S(u,i) C(n-i,k-i). That identity checks out numerically and matches the known Moser form. The reduction from k-subset sums to power sums via Newton identities and Vieta is coherent, and the authors are honest about the invertibility condition. The connection to singular pairs is a useful extension of the Selfridge-Straus/Fomin program.\n\nSoft spots, in order: (1) Algorithm 2's line 13 should break when the partition length exceeds k, i.e., 'n(L[j]) > k', not 'k > n(L[j])'; as printed the first partition (u) has length 1, k≥2, so it breaks immediately and M stays all zeros. Line 3's 'if [Moser expression]' triggers failure when the expression is nonzero, i.e., exactly when Theorem 2 says the algorithm should work. (2) The root-finding step (line 32) is numerical in the cited method; the deterministic exact-recovery guarantee needs an explicit real-computation model or error analysis. (3) The proof of Theorem 3 is compressed—the cofactor argument that identifies the coefficients with Stirling numbers is hard to audit; an expanded proof or a formal check would help. (4) Section 4.6 says 'No with high probability' in a deterministic context; that phrasing should be separated or reworded. Also, the novelty claim about 'no deterministic algorithms' should be verified against the literature more carefully, and the absence of code or experiments weakens reproducibility but doesn't invalidate the math.\n\nWho gets value: people working on multiset recovery, additive combinatorics, and privacy attacks on aggregate statistics. The paper deserves a serious referee, but with the expectation of a major revision: fix the pseudocode, expand Theorem 3, and state the computation model. I'd accept after that.","headline":"Solid symmetric-polynomial algorithm for the (n,k)-complete HSSP, but Algorithm 2's pseudocode has inverted conditions and the exact-real assumption is unaddressed.","tokens_in":18520,"tokens_out":3328,"would_cite":true,"duration_ms":31828,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05E05","05A17","11P81","11B73"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes a deterministic algebraic algorithm for the $(n,k)$-complete hidden subset sum problem: from the multiset of all $k$-subset sums it recovers the hidden multiset $X$ as the roots of a degree-$n$ polynomial, whenever a…","keywords":["hidden subset sum problem","multiset recovery","symmetric polynomials","power sums","elementary symmetric polynomials","integer partitions","deterministic algorithm","singular parameter pairs"],"falsifier":"Run the paper's symmetric subset sum recovery algorithm on a small non-singular instance with known data, for example $X=\\{1,2,3,4,5\\}$ with $k=2$, in the paper's exact-arithmetic model on the ten pairwise sums; if the output multiset differs from $X$, the recovery claim is false. Separately, compute Matrix (1) for a small pair such as $n=5,k=2,u=3$ and compare its numerical determinant with $\\sum_{i=1}^u(-1)^{i-1}(i-1)!\\,S(u,i)\\binom{n-i}{k-i}$; any mismatch would falsify the closed-form determinant theorem.","tokens_in":17620,"feed_emoji":"🧮","tokens_out":16585,"duration_ms":137642,"temperature":0.7,"pith_summary":"The paper proposes two deterministic algorithms for the $(n,k)$-complete hidden subset sum problem, in which one must recover a multiset $X$ of $n$ real numbers from the multiset of all $\\binom{n}{k}$ sums of $k$ distinct elements. One is an ordering-pruned brute-force search; the other is an algebraic recovery method. The algebraic method converts the subset-sum data into power sums $S_u$ of the given sums, solves a sequence of square linear systems whose unknowns are symmetric polynomials of $X$ indexed by integer partitions of $u$, and obtains the elementary symmetric polynomials $e_1,\\dots,e_n$. From those it builds the degree-$n$ polynomial $x^n-e_1x^{n-1}+\\cdots+(-1)^n e_n$, whose roots are exactly the hidden elements. The recovery is guaranteed whenever a certain determinant is nonzero for every $u=1,\\dots,n$; the paper computes that determinant in closed form and shows that its vanishing is the condition previously known to control the uniqueness of solutions. If the condition holds, the deterministic runtime is $O\\!\\big(\\sum_{u=1}^n p(u,\\le k)^3+\\binom{n}{k}n\\big)$, where $p(u,\\le k)$ counts partitions of $u$ into at most $k$ parts.","feed_headline":"Deterministic algorithm recovers hidden numbers from subset sums","feed_subtitle":"No search, no randomness: the hidden multiset is read off as the roots of one polynomial.","key_machinery":"The key object is a square matrix (Matrix (1) in the paper) whose rows and columns are labelled by partitions of $u$ into at most $k$ parts. Its first row records the coefficients that express the $u$-th power sum $S_u$ of the subset-sum data in terms of the partition-indexed symmetric polynomials of $X$; the other rows record coefficients that express products of lower-degree power sums in the same basis. Invertibility of this matrix for every $u=1,\\dots,n$ is what lets the algorithm determine all elementary symmetric polynomials of $X$. The second ingredient is the coefficient–root relation: a monic degree-$n$ polynomial is fixed by its elementary symmetric coefficients, and its roots are precisely the elements of $X$. The paper derives the determinant of Matrix (1) in closed form and uses it to identify the $(n,k,u)$ combinations where the linear system collapses.","core_discovery":"The central discovery is that the entire algebraic content of the $(n,k)$-complete HSSP can be organized as a sequence of square linear systems. For each degree $u$, the $u$-th power sum $S_u$ of all $k$-subset sums is a linear combination of the symmetric polynomials indexed by partitions of $u$, with binomial and multinomial coefficients; products of lower-degree power sums supply the remaining rows of the coefficient matrix. The paper proves that this matrix is invertible exactly when $\\sum_{i=1}^u (-1)^{i-1}(i-1)!\\,S(u,i)\\binom{n-i}{k-i}\\neq 0$, equivalently $\\sum_{j=1}^k (-1)^{j-1}j^{u-1}\\binom{n}{k-j}\\neq 0$. When this holds for every $u$, the elementary symmetric polynomials are uniquely determined, standard power-sum identities fill in the higher ones, and the hidden multiset is recovered as the roots of the polynomial built from those coefficients. The paper also proves that if the first failure occurs at degree $u_0$, no basis for the degree-$u$ homogeneous symmetric polynomial ring with $u\\ge u_0$ can be constructed from the available subset-sum power sums, so the obstruction is intrinsic to the data.","pith_inferences":["Read as a complexity statement, the bound implies polynomial time for every fixed $k$: since $p(u,\\le k)=O(u^{k-1})$, the summed term is polynomial in $n$, so the algebraic method is an explicit polynomial-time deterministic route on all non-singular instances with $k$ fixed.","Because the determinant has a closed form, an implementation can check all $u=1,\\dots,n$ symbolically before solving any linear system, turning the singularity condition into a certificate that either guarantees recovery or identifies the first failing degree.","The method invites stress-testing on partial or noisy versions of the problem, such as recovering $X$ from a proper subset of the $k$-subset sums; Theorem 4 rules out symmetric subsets that carry full information, but it leaves asymmetric partial samples unexplored.","The tight link between the determinant and the classical uniqueness condition suggests using the algorithm as a constructive uniqueness witness: on non-singular pairs it not only shows that a solution exists but exhibits it."],"forward_implications":["On every instance that satisfies the nonzero-determinant condition for $u=1,\\dots,n$, the hidden multiset is recovered in deterministic worst-case time $O\\!\\big(\\sum_{u=1}^n p(u,\\le k)^3+\\binom{n}{k}n\\big)$, with no random choices and no lattice assumptions.","The determinant condition is the same polynomial that the classical uniqueness theory uses; when it vanishes, the classical sufficient condition for uniqueness no longer applies and the algorithm's linear systems collapse.","For fixed $k$, the determinant is a degree-$(k-1)$ polynomial in $n$, so the singular values of $n$ are constrained by divisibility: any such $n$ must divide $(k-1)!\\,k^{u-1}$; for $k=2$ the only failures occur at $n=2^{u-1}$.","If the first singular degree is $u_0$, then no basis of the degree-$u$ symmetric polynomial ring for $u\\ge u_0$ can be constructed from the subset-sum power sums alone, so unique recovery is impossible from that data without extra information.","The algebraic recovery method transfers to any field or ring in which $n!$ and each determinant value are invertible and the coefficient–root relations hold, provided the arithmetic is exact."],"supporting_citations":[{"why":"Supplies the symmetric-function framework and the classical nonzero-polynomial condition that the paper's determinant is shown to reproduce.","marker":"[10]"},{"why":"Defines the multiset recovery formulation and the singularity vocabulary in which the problem and its uniqueness condition are stated.","marker":"[6]"},{"why":"Provides the binomial identity used to identify the determinant of Matrix (1) with the classical condition.","marker":"[12]"},{"why":"Gives the coefficient–root relations that turn the recovered elementary symmetric polynomials into the polynomial whose roots are $X$.","marker":"[23]"},{"why":"Defines the Stirling partition numbers that appear in the closed-form determinant of Matrix (1).","marker":"[25]"},{"why":"Defines integer partitions and the partition-counting function that determine the matrix size and the complexity bound.","marker":"[24]"},{"why":"Supplies the cost of solving linear systems and of computing polynomial roots used in the complexity analysis.","marker":"[26]"},{"why":"Supplies the companion-matrix root-finding method behind the polynomial-root step in the algorithm.","marker":"[28]"}],"fun_headline_variants":["Deterministic algorithm solves hidden subset sum problem","Hidden subset sums recovered as polynomial roots","No search, no randomness: subset sums yield polynomial roots","Vieta's formulas turn subset sums into hidden numbers","Deterministic recovery of hidden multiset from subset sums"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The deterministic guarantee assumes an idealized exact-arithmetic model in which power sums, matrix inversions, and the roots of the degree-$n$ polynomial are computed exactly; the paper gives no error analysis for the numerical root-finding step, so the guarantee need not survive floating-point rounding.","fun_headline_variants_meta":{"raw":{"variants":["Deterministic algorithm solves hidden subset sum problem","Hidden subset sums recovered as polynomial roots","No search, no randomness: subset sums yield polynomial roots","Vieta's formulas turn subset sums into hidden numbers","Deterministic recovery of hidden multiset from subset sums"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001007,"raw_usage":{"total_tokens":4277,"prompt_tokens":983,"completion_tokens":3294,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":3220}},"tokens_in":599,"tokens_out":3294,"duration_ms":19705,"temperature":1.0,"reasoning_tokens":3220,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T21:09:09.459875+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's symmetric subset sum recovery algorithm on a small non-singular instance with known data, for example $X=\\{1,2,3,4,5\\}$ with $k=2$, in the paper's exact-arithmetic model on the ten pairwise sums; if the output multiset differs from $X$, the recovery claim is false. Separately, compute Matrix (1) for a small pair such as $n=5,k=2,u=3$ and compare its numerical determinant with $\\sum_{i=1}^u(-1)^{i-1}(i-1)!\\,S(u,i)\\binom{n-i}{k-i}$; any mismatch would falsify the closed-form determinant theorem.","supporting_citations":[{"cited_title":"On the determinatio n of numbers by their sums of a fixed order","cited_arxiv_id":null,"evidence_quote":"Supplies the symmetric-function framework and the classical nonzero-polynomial condition that the paper's determinant is shown to reproduce."},{"cited_title":"Is the multiset of n integers uniquely det ermined by the multiset of its s-sums? The American Mathematical Monthly , 126(5):400– 417, 2019","cited_arxiv_id":null,"evidence_quote":"Defines the multiset recovery formulation and the singularity vocabulary in which the problem and its uniqueness condition are stated."},{"cited_title":"On the determination of sets by sets of sums of fixed order","cited_arxiv_id":null,"evidence_quote":"Provides the binomial identity used to identify the determinant of Matrix (1) with the classical condition."},{"cited_title":"Algebra, volume 211","cited_arxiv_id":null,"evidence_quote":"Gives the coefficient–root relations that turn the recovered elementary symmetric polynomials into the polynomial whose roots are $X$."},{"cited_title":"Enumerative Combinatorics Volume 1 second edition","cited_arxiv_id":null,"evidence_quote":"Defines the Stirling partition numbers that appear in the closed-form determinant of Matrix (1)."},{"cited_title":"Integer partitions","cited_arxiv_id":null,"evidence_quote":"Defines integer partitions and the partition-counting function that determine the matrix size and the complexity bound."},{"cited_title":"Numerical Linear Algebra","cited_arxiv_id":null,"evidence_quote":"Supplies the cost of solving linear systems and of computing polynomial roots used in the complexity analysis."},{"cited_title":"Polynomial roots fr om companion matrix eigenvalues","cited_arxiv_id":null,"evidence_quote":"Supplies the companion-matrix root-finding method behind the polynomial-root step in the algorithm."}],"review_version":1}