It's well known you can find a solution to the linear Diophantine equation

\[ a_1x_1 + a_2x_2 + \ldots + a_nx_n = c \]

in polynomial time using the Extended Euclidean Algorithm. But I haven't been able to find a clear answer for the complexity of finding a non-negative integer solution, that is, \( x_i \geq 0 \).

The unbounded knapsack problem is NP-complete, and this is the case where the weights and costs are equal, but I'm not sure that the NP-hardness reduction applies given that additional constraint.

I have also found a statement that the "multidimensional knapsack problem" is NP-hard even with a single row, which seems to match this, but I lack a copy of Papadimitriou and Steiglitz to verify that statement, and can't figure out the reduction.

If this problem is NP-hard, then I'm also interested in showing that a related problem is also NP-hard: if we have one non-negative solution, can we find a second one? I'm trying to answer a question about the special case \( c = \sum_{i=1}^{n} a_i \).

#ComputationalComplexity #diophantine

If I'm really committed to the fact that there is no such thing as actual infinity - and I am: https://www.wisdomneverdies.com/blog/no-infinity -
then there are no actual irrational numbers. By Kronecker's Theorem then, all apparently chaotic behavior is ultimately periodic. An interesting corollary 🙂

#infinity #math #philosophy #Cavendish #Cantor #Locke #Aristotle #Knuth #chaos #Kronecker #Diophantine

Over on Quora, I answered a question about integer solutions to \( a^2 - b^2 = b^2 - c^2 \). If we rewrite it as \( a^2 - 2b^2 = -c^2 \) it becomes clear that it's a general Pell equation. It looks like we get a nontrivial family of solutions whenever \( c \) is a prime that is +1 or -1 mod 8, but I'm not seeing why that should be.

https://www.quora.com/Equally-spaced-squares-Is-it-possible-to-find-a-b-c-such-that-a%C2%B2-b%C2%B2-b%C2%B2-c%C2%B2-please-give-examples-and-conditions-of-proof-against/answer/Mark-Gritter

For c = 1 this is exactly the negative Pell equation, so we have solutions like \( 7^2 - 5^2 = 5^2 - 1^2 \). c = 17 gives us a pair of infinite families starting with \( 7^2 - 13^2 = 13^2 - 17^2 \) and \( 31^2 - 25^2 = 25^2 - 17^2 \).

c = 5783 has primitive solutions a = 4369, b = 5125 and a = 7393, b = 6637.

Can we show that there is always a nontrivial solution for primes of this form?

#diophantine #numbertheory