Re: Looking for a smaller solution...

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Feb 02, 2023 at 01:22:40PM -0600, wraithx@morpheus.net wrote:
> 
> Speaking of, thank you for the suggestions for finding all solutions with
> the extra option to matsolvemod.  And thank you for the suggestion of
> 
> A=matconcat([M,E;0,1]);U=qflll(A);A*U
> 
> I was finally able to run this on my full dataset (of 1248 primes) and A*U
> was a matrix of size 1249x1249, and it took about 25 minutes, and 42GB, to
> calculate.  There was only a single column that had a 1 in the last row
> (every other column had a 0 in the last row).  In that last column, 1068
> entries were 0, 90 were greater than 0, and 91 were less than 0.  The most
> negative number was -1365, the most positive was 1061.  I was hoping to get
> all non-negative values for the exponents.  Is there a way get all the
> entries to be >= 0?  Thanks again for any advice!

It depends what you expect, for example how many primes are likely to 
appear in the solution, what should be the exponents, etc.

Note that your question makes sense with negative exponents too.

First, you can always try small combinations of the vector to see if you get
something positive.

In the general case, this is an integer linear programming problem.
You need to use ILP software, I usually use 
normaliz <https://www.normaliz.uni-osnabrueck.de/>

However your matrix is huge so this might take too long.
You might want to start by discarding most of the rows corresponding to the 0
entries, hoping the corresponding primes do not appear in the solution.

Cheers,
Bill.