On the subset sum problem for finite fields

DOI10.1016/J.FFA.2021.101912MaRDI QIDQ2238923zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 2 November 2021

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ffa.2021.101912

zbMATH Keywords

finite fieldsubset sumsubset sum problemzero sumsetzero-sum set

Mathematics Subject Classification ID

Partitions of sets (05A18) Other combinatorial number theory (11B75) Inverse problems of additive number theory, including sumsets (11P70)

Review text

Let \(G\) be the additive group of a finite field. We discuss the number of representations of elements of \(G\) as a sum of \(k\) distinct elements of \(G\), the so-called subset sum problem. \textit{J. Li} and \textit{D. Wan} [Finite Fields Appl. 14, No. 4, 911--929 (2008; Zbl 1189.11058)] 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 an expression for the case where the subsets are required to contain only nonzero elements. The paper under review gives an alternative proof of the two formulas. The new combinatorial approach is different from original combinatorial approach by Li and Wan, and indicates some new connections with coding theory and combinatorial designs.

Recommendations

• The subset sum problem for finite abelian groups
• On the subset sum problem over finite fields
• The \(k\)-subset sum problem over finite fields of characteristic 2
• An asymptotic formula for counting subset sums over subgroups of finite fields
• The \(k\)-subset sum problem over finite fields

Cites work

• Additivity of affine designs
• An addition theorem for Abelian groups of order pq
• Binary Hamming codes and Boolean designs
• scientific article; zbMATH DE number 3178047 (Why is no real title available?)
• On Deciding Deep Holes of Reed-Solomon Codes
• On the addition of residue classes mod p
• On the additivity of block designs
• On the condensation points of the Lagrange spectrum
• On the subset sum problem over finite fields
• Perfect binary codes: constructions, properties, and enumeration
• Permutations of zero-sumsets in a finite vector space
• Subset sums and block designs in a finite vector space
• The subset sum problem for finite abelian groups

Cited in

(18)

• The \(k\)-subset sum problem over finite fields
• Linear subspaces of finite fields with large inverse-closed subsets
• The subset sum problem for finite abelian groups
• Super-regular Steiner 2-designs
• Laced Boolean functions and subset sum problems in finite fields
• Subsets in linear spaces over the finite field F₃ uniquely determined by their pairwise sums collection
• Moment subset sums over finite fields
• The \(k\)-subset sum problem over finite fields of characteristic 2
• Sum uniform subsets of the integers modulo p and an application to finite fields
• The number of sumsets in a finite field
• scientific article; zbMATH DE number 1315277 (Why is no real title available?)
• Power sums over subspaces of finite fields
• scientific article; zbMATH DE number 2188380 (Why is no real title available?)
• A new family of additive designs
• Subset sums and block designs in a finite vector space
• Subset sums over Galois rings. II
• An asymptotic formula for counting subset sums over subgroups of finite fields
• On the subset sum problem over finite fields

This page was built for publication: On the subset sum problem for finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2238923)