Timeline for Nonexistence of short integer program sequence which generates squares
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 17 at 16:17 | review | Low quality posts | |||
| Jul 17 at 23:31 | |||||
| Jul 16 at 17:48 | history | edited | joro | CC BY-SA 4.0 |
tried the significantly rewritten question
|
| Jul 16 at 16:56 | comment | added | Turbo | @joro At this point you should remove your answer since even for the very first version of the question, your answer was not a proof but merely consequence of existence of such a program. | |
| Jul 16 at 12:22 | comment | added | joro | @ClaudeChaunier Besides answering that a value is square, I rely on actually computing the solution. Given a program which expresses exactly the set {m^2}, I use two copies of the IP program to find X=u^2=m_0^2 and Y=v^2=m_1^2 and then the solution. | |
| Jul 16 at 12:16 | comment | added | Claude Chaunier | I don't get it. How would we go from a program that answers whether a variable takes only square values to a program that answers whether two variables have some feasible square values (and possibly feasible non-square values as well)? | |
| Jul 15 at 16:58 | comment | added | Turbo | That is not a proof. A proof should be able to quantify how many variables are needed etc.. Or at least be a proof by contradiction of some sort.. but it should reveal something. | |
| Jul 15 at 16:45 | comment | added | joro | @Turbo I think if you can express the infinite sets with O(1) variables, you will factor all integers with O(1) variables. When you express multiplication in IP, you need something like log_2(N) variables and it depends on N. | |
| Jul 15 at 16:24 | comment | added | Turbo | @joro " there is no way to describe such infinite set..." why is that? That is the question here. | |
| Jul 15 at 16:03 | comment | added | joro | @Turbo I think unless you give bound on the solution, there is no way to describe such infinite set with linear constraints. But even with a bound, probably solving $X Y=N$ is more integer programming friendly. | |
| Jul 15 at 15:48 | comment | added | Turbo | Sure.. factoring was the reason for the question... it is obvious one can factor. Indeed one can show #P is in FP if this is true. So it seems there should be a proof for the O(1) case. | |
| Jul 15 at 12:36 | history | edited | joro | CC BY-SA 4.0 |
addressed comment
|
| Jul 15 at 12:04 | comment | added | joro | @PeterTaylor Indeed, there are some other constraints on X,Y to be added. | |
| Jul 15 at 11:51 | comment | added | Peter Taylor | To spell out an important detail, if $M$ is a large odd number then taking $N=M$ doesn't work, because $u-v = 1$ gives a trivial solution, but taking $N=2M$ does work because $u-v=2$, $u+v = M$ runs into parity problems. | |
| Jul 15 at 8:39 | history | answered | joro | CC BY-SA 4.0 |