Applications Of The Subset Sum Problem Over Finite Abelian Groups

Given a finite abelian group $G$, a finite set $D$, and a mapping $f:D\rightarrow G$, we find the number of $r$-subsets $S\subseteq D$ where for $b\in G$, \begin{align*} \sum_{x\in S}f(x)=b. \end{align*} We obtain simple exact expressions when $f$ is an abelian group homomorphism. When $G=\Fq$, we extend known results when D\in\{\Fq,\Fq^*\} and f(x)=x^N, which include quadratic and semiprimitive cases. We count degree $n$ monic polynomials over $\Fq$ with $r$ distinct roots in a set $D\subseteq\Fq$ when the leading terms of degree at least $n-\ell$ are fixed. We obtain new formulas for $\ell=1$ when $D$ is a multiplicative subgroup of \Fq^*, and for $\ell=2$ when $D$ is an arbitrary subfield of $\Fq$ with $q$ odd.

Name thesis:degree_name

Master of Science (M.Sc.)

Level thesis:degree_level

Master's

Discipline thesis:degree_discipline

Mathematics

Grantor dc:publisher

Carleton University

Year dc:date.issued

2023

Author dc:creator

• Kuttner, Simon Martial

Statement dc:rights

• Copyright © 2023 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, distribution to students, research and scholarship. Theses may only be shared by linking to the Carleton University Institutional Repository and no part may be copied without proper attribution to the author; no part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.

Language dc:language.iso

en

DOI

10.22215/etd/2023-15572

OAI identifier oai:identifier

oai:carleton.scholaris.ca:20.500.14718/40861