How hard is finding values such that

Question

We can work with powers of some naturals $(x_k)^{m_k}$. Here we have $n$ naturals, and $m_k$ is an integer in the range $-r$ to $r$. My question is, how small can $p$ be so that

$$\prod_{k=1}^n{(x_k)^{m_k}}$$

is unique for any collection of $m_k$'s? In other words, for any set of $k$ integers of one's choosing, how small can we make $p$ so that the product above is always unique? The answer doesn't have to be perfect. Even a general idea would be good.

AN EXAMPLE

Let $n=2$.

Then we can pick $x_1=2$ and $x_2=3$, and find that $p=31$ works. We could choose any $x$'s we like, in order to get a smaller $p$.

and here's a table of powers:

\begin{array}{c|c|c|c|c|c|} \times & 2^{-2} & 2^{-1} & 2^0 & 2^1 & 2^2 \\ \hline 3^{-2} & 25 & 19 & 7 & 14 & 28 \\ \hline 3^{-1} & 13 & 26 & 21 & 11 & 22\\ \hline 3^0 & 8 & 16 & 1 & 2 & 4\\ \hline 3^1 & 24 & 17 & 3 & 6 & 12 \\ \hline 3^2 & 10 & 20 & 9 & 18 & 5 \\ \hline \end{array}

So by picking the $x$'s carefully, we have made sure that all powers from $-2$ to $2$ for both numbers is unique. And this then works for $p=31$, as shown.

THE QUESTION, AGAIN

We're given $n$ and $r$, and wish to solve for $p$.

So if we have $n$ values of $x$ (of our choosing - they're not given - they can help make the problem easier), and we are interested in all powers between $-r$ and $r$, how small can $p$ be?

ANOTHER TIDBIT

I'm wondering if this would be considered research-level mathematics. Perhaps someone can answer this?

Answer 1

Fleshing out my comment to an answer/suggestion.

Let's first look at an additive version. We know that that the sums $$ S(m_0,m_1,\ldots,m_{n-1}):=\sum_{k=0}^{n-1}m_k(2r+1)^{k-1}, $$ with all the $m_k$ ranging over $\{-r,-r+1,\ldots,-1,0,1,\ldots,r-1,r\}$, are distinct (sorta like writing integers in base $2r+1$) and in the interval from $-\left((2r+1)^n-1\right)/2$ to $\left((2r+1)^n-1\right)/2$, i.e. of length $<(2r+1)^n$.

Next we proceed to map this to the domain of modular multiplication. To that end let us pick a prime $p>(2r+1)^n$. Further let $g$ be a primitive root modulo $p$. It is well known that $g^i\equiv g^j\pmod p$ if and only if $i\equiv j\pmod{p-1}$. Therefore all the powers $g^{S(m_0,m_1,\ldots,m_{n-1})}$ are pairwise non-congruent modulo $p$.

This implies that the choice $x_i=g^{(2r+1)^{i-1}}$, $i=1,2,\ldots,n$ fulfills Matt's requirements. This is because $$ \prod_{k=1}^nx_k^{m_k}\equiv g^{S(m_0,m_1,\ldots,m_{n-1})}\pmod p. $$

As an example consider the case $n=2$, $r=3$. Now $(2r+1)^2=49$, so we can select $p=53$. It is easy to show that $g=2$ is a primitive root, so we select $x_1=2$. We further select $x_2=22$ as $x_1^7=128\equiv22\pmod{53}$. As a final confirmation let me represent the table of remainders of $2^i\cdot 22^j$ modulo $53$: $$ \begin{array}{c|ccccccc} i\backslash j&-3&-2&-1&0&1&2&3\\ \hline\\ -3&49& 18& 25& 20& 16& 34& 6\\ -2&45& 36& 50& 40& 32& 15& 12\\ -1&37& 19& 47& 27& 11& 30& 24\\ 0&21& 38& 41& 1& 22& 7& 48\\ 1&42& 23& 29& 2& 44& 14& 43\\ 2&31& 46& 5& 4& 35& 28& 33\\ 3&9&39& 10& 8& 17& 3& 13 \end{array} $$

As an example with $n=3$, $r=2$, $(2r+1)^n=125$ we use $p=127$. This time we can use $x_1=g=3$, $x_2=116\equiv 3^5\pmod{127}$ and $x_3=112\equiv x_2^5\pmod{127}$. I hope I can be excused for failing to provide the resulting 3-dimensional table of 125 entries.

It is clear that the density of prime numbers is high enough so that we need not go much above the limit $(2r+1)^n$.

Answer 2

Here' sort of a baseline answer. It doesn't provide a very good bounds, but we can prove it works. Please pardon my description, as I know it could be a lot better. Any suggestions that will improve this are welcome.

So we start with $n$ values, and we want to ensure they're unique when we use the given function in the question.

We also start knowing the powers range from $-r$ to $r$. This means that we'll be using $2r + 1$ powers of each number.

So, we can start by choosing the $x$ values to be the $n$ smallest primes. Then we know that we'll have each $x$ value range from $x^{-r}$ to $x^r$, inclusive. We temporarily change this range of powers to be from $x^0$ to $x^{2r}$, inclusive, which will give us $2r + 1$ powers.

Then if we pick a prime that is greater than

$$\prod_{k=1}^n{(x_k)^{2r}} = (x_1)^{2r} \cdot (x_2)^{2r} \cdot (x_3)^{2r}\dots (x_n)^{2r} \tag{1}$$

...all of these new powers are guaranteed to be unique. That is because the factorization of each number in this form is unique from any other number of this form, since we are using primes. In other words, we have created a unique factorization by using this form.

Now, since we are working modulo a prime, and hence also working with a finite field, we know that we can multiply by $(x_k)^{-r}$ for any $x^k$ and the values in the above function will still be unique.

Thus we can now multiply all of the values in the above function by:

$$\prod_{k=1}^n{(x_k)^{-r}} = (x_1)^{-r} \cdot (x_2)^{-r} \cdot (x_3)^{-r}\dots (x_n)^{-r} \tag{2}$$

And this will give us the function for our original range. Thus we have proved that we can get the unique values that we are after by picking ANY $p$ such that $p$ is prime and greater than Equation (1).