A $\bmod p$ version of the Frobenius coin problem.

52 Views Asked by At

Let $x_1,\dots,x_d$ be $d$ integers having greatest common divisor equal to $1$. By Bézout's Lemma, there exists a least $\kappa(x_1,\dots,x_d) \in \mathbb{N}$ such that any $k \geq \kappa(x_1,\dots,x_d)$ can be written as $k = \alpha_1x_1+\dots+ \alpha_dx_d$, where $\alpha_j \in \mathbb{N}$. The Frobenius coin problem ask for estimating $\kappa_d = \max_{x_1,\dots,x_d\in\mathbb{Z}}\kappa(x_1,\dots,x_d)$.

During my research, I came up with the following variation of the Frobenius problem, which takes place in $\mathbb{Z}/p\mathbb{Z}$ instead of $\mathbb{Z}$ and which has some additional constrains on the allowed coefficients $\alpha_j$. Any comment about it is appreciated.

Does there exists $d \in \mathbb{N}$ having the following property? For every prime number $p$ and for every sequence $n_1,n_2,\dots$ in the field $F_p = \mathbb{Z}/p\mathbb{Z}$ we can find $k_1,\dots,k_d \subseteq F_p$ such that each $n_j$ can be written as $$n_j = \alpha_{1,j}k_1 + \alpha_{2,j}k_2 + \dots +\alpha_{d,j}k_d, \text{ where $0\leq \alpha_{1,j},\dots,\alpha_{d,j} \leq 3^j$.}$$