0
$\begingroup$

Let $p \in \mathbb{N}$ be a composite number and let $x, y$ be vectors with elements from $\mathbb{Z}_p$ of some fixed length (in my case it's 39). How to find such $k \in \mathbb{Z}_p$ that the value below is minimized? $$ \max(f(x + ky))) $$ Here, $\max$ is just maximum value of vector entries, while $f$ is the inclusion map from $\mathbb{Z}_p$ to $\mathbb{Z}$.

I'm looking for practical solutions. In my case $k = 39$ and $p = 311^2 \cdot 313^2 \cdot 317^2 \cdot 331^2 \cdot 337^2 \cdot 347^2 \cdot 349^2 \cdot 353^2$. The brute force search over all values of $k$ is impossible.

Another version of the problem is as follows:

Given $0 \leq \nu < p$, find $k \in \mathbb{Z}_p$ such that $$ \max(f(x + ky))) < \nu $$

Is there any clever approach to any of the problems?

As an addendum, here's example on what exact function I want to minimize. Let $p = 10$, $k = 3$. Here's example in Python:

p = 10
x = [4, 3, 8]
y = [1, 5, 0]
for v in range(p):
    print(max([(e+v*f) % 10 for e, f in zip(x, y)]))

Output:

9 6 9 5 7 9 4 4 7 7

So here, we know that the minimum is at $v = 6$ or $v = 7$.

$\endgroup$
  • $\begingroup$ @Macavity no, that's just my sloppiness in the code (sorry) $\endgroup$ – enedil Dec 30 '18 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.