6533b860fe1ef96bd12c2f7c
RESEARCH PRODUCT
On the subset sum problem for finite fields
Marco Pavonesubject
Discrete mathematicsAlgebra and Number TheoryApplied MathematicsGeneral EngineeringSubset sumFinite fieldCoding theoryExpression (computer science)Zero-sum setTheoretical Computer ScienceFinite fieldCombinatorial designSettore MAT/05 - Analisi MatematicaSubset sum problemSettore MAT/03 - GeometriaElement (category theory)Argument (linguistics)Subset sum problemZero sumsetAdditive groupMathematicsdescription
Abstract Let G be the additive group of a finite field. J. Li and D. Wan determined the exact number of solutions of the subset sum problem over G, by giving an explicit formula for the number of subsets of G of prescribed size whose elements sum up to a given element of G. They also determined a closed-form expression for the case where the subsets are required to contain only nonzero elements. In this paper we give an alternative proof of the two formulas. Our argument is purely combinatorial, as in the original proof by Li and Wan, but follows a different and somehow more “natural” approach. We also indicate some new connections with coding theory and combinatorial designs.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2021-12-01 |