Timeline for How can you find an integer coefficient polynomial knowing its values only at a few points (but requiring the coefficients be small)?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 28, 2021 at 19:48 | comment | added | Max Alekseyev | @AlexanderChervov: Yes and No. In this context, LLL solves problem in $\ell^2$ norm, while ILP does that in $\ell^\infty$ norm; LLL solves the problem approximately, ILP does that exactly. | |
| Sep 28, 2021 at 19:03 | comment | added | Alexander Chervov | By the way does it mean the LLL can be applied to some class of ILP problems ? | |
| Sep 28, 2021 at 18:06 | comment | added | Max Alekseyev |
@PabloH: I've checked with a locally installed Gurobi solver, and with degree=20 it produces the same polynomial as with degree=10.
|
|
| Sep 28, 2021 at 17:59 | comment | added | Max Alekseyev | @PabloH: That is an issue with the ILP solver (by default SageCell uses GPLK), which sometimes does too much relaxation and inadvertently violates some of the given constraints. This can be remediated by tightening solver parameters or switching to an exact solver (which may be time costly). | |
| Sep 28, 2021 at 14:17 | comment | added | Alexander Chervov | @PabloH [ 221980., 56972656.] seems to be different values for the second polynom, than required | |
| Sep 28, 2021 at 14:07 | comment | added | Alexander Chervov | @PabloH strange | |
| Sep 28, 2021 at 13:56 | comment | added | Pablo H |
For $d=10$, best_poly([3,5],[221157,31511625],10) gives $2*z^{10} + 7*z^9 - 3*z^8 - 6*z^7 - 4*z^6 + 3*z^5 + 4*z^4 - 2*z^3 + 2*z - 6$ (Best bound: 7), while for $d=20$ best_poly([3,5],[221157,31511625],20) gives $z^{11} + z^{10} - z^9 + z^8 - z^7 + z^6 + z^5 + z^4 + z^3 + z^2 + z + 1$ (Best bound: 1).
|
|
| Sep 28, 2021 at 13:10 | history | answered | Max Alekseyev | CC BY-SA 4.0 |