Solve system of inequalities modulo
$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$.
number-theory inequality modular-arithmetic nonlinear-optimization
asked Dec 30 '18 at 0:02
enedilenedil
1,174619
$endgroup$
add a comment |
$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$.
number-theory inequality modular-arithmetic nonlinear-optimization
asked Dec 30 '18 at 0:02
enedilenedil
1,174619
$endgroup$
$begingroup$
@Macavity no, that's just my sloppiness in the code (sorry)
$endgroup$
– enedil
Dec 30 '18 at 2:04
add a comment |
$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$.
number-theory inequality modular-arithmetic nonlinear-optimization
asked Dec 30 '18 at 0:02
enedilenedil
1,174619
$endgroup$
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$.
number-theory inequality modular-arithmetic nonlinear-optimization
number-theory inequality modular-arithmetic nonlinear-optimization
asked Dec 30 '18 at 0:02
enedilenedil
1,174619
asked Dec 30 '18 at 0:02
enedilenedil
1,174619
edited Dec 30 '18 at 2:03
enedil
asked Dec 30 '18 at 0:02
enedilenedil
1,174619
asked Dec 30 '18 at 0:02
enedilenedil
1,174619
asked Dec 30 '18 at 0:02
enedilenedil
1,174619
1,174619
$begingroup$
@Macavity no, that's just my sloppiness in the code (sorry)
$endgroup$
– enedil
Dec 30 '18 at 2:04
add a comment |
$begingroup$
@Macavity no, that's just my sloppiness in the code (sorry)
$endgroup$
– enedil
Dec 30 '18 at 2:04
$begingroup$
@Macavity no, that's just my sloppiness in the code (sorry)
$endgroup$
– enedil
Dec 30 '18 at 2:04
$begingroup$
@Macavity no, that's just my sloppiness in the code (sorry)
$endgroup$
– enedil
Dec 30 '18 at 2:04
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3056383%2fsolve-system-of-inequalities-modulo%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3056383%2fsolve-system-of-inequalities-modulo%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
@Macavity no, that's just my sloppiness in the code (sorry)
$endgroup$
– enedil
Dec 30 '18 at 2:04