On the subset sum problem for finite fields
| Autor: | Marco Pavone |
|---|---|
| Přispěvatelé: | Marco Pavone |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Discrete mathematics
Algebra and Number Theory Applied Mathematics General Engineering Subset sum Finite field Coding theory Expression (computer science) Zero-sum set Theoretical Computer Science Combinatorial design Settore MAT/05 - Analisi Matematica Subset sum problem Settore MAT/03 - Geometria Element (category theory) Argument (linguistics) Zero sumset Additive group Mathematics |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|