Wikipedia:Reference desk/Archives/Mathematics/2024 October 15

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 15

Is this really a prime-generating polynomial?

In this article, an inequality involving a set of Diophantine equations is given as an example. But does that even qualify as a "formula for primes"? It looks more like a primality test of sorts, ie iff the inequality holds then (k + 2) is prime, so one would still need to generate a likely prime candidate to begin with. Which brings me to the next issue. Setting all of the variables to positive integers and then k to "some prime minus two", the inequality fails regardless. So there must be some special set of rules for selecting the values for each variable? Earl of Arundel (talk) 20:48, 15 October 2024 (UTC)

The inequality only fails if one of the terms isn't zero. If all terms are zero, then the polynomial evaluates to k+2. Thus, the set of primes is precisely the set of positive values taken by this function. The arguments needed to produce the primes are not constructed, but one imagines plotting the function for all integer values of the arguments. Tito Omburo (talk) 21:59, 15 October 2024 (UTC)

Sorry, I don't quite understand. I thought none of the 26 variables could be zero? Also, the fact that "the primes are not constructed" leads me to believe that this is indeed not a "prime-generating polynomial" per se. Is that correct? Earl of Arundel (talk) 23:00, 15 October 2024 (UTC)

The terms alpha_i have a simultaneously zero only when k+2 is prime. So the sum of the squares of the alpha_i always exceeds one unless k+2 is prime. I don't know what "prime generating polynomial" means. This is certainly a polynomial whose range in the positive integers consists only of the primes. Tito Omburo (talk) 23:06, 15 October 2024 (UTC)

Perhaps it's not that obvious from the article, but the polynomial is not meant to be a practical method for generating primes. Plugging in random values for the variables will give positive, hence prime, values only a small fraction of the time. Finding values of the variables for which the polynomial is positive will be at least as difficult as just computing primes using conventional methods. The point is demonstrate that such a function is possible, but that doesn't mean you'd actually use it. It's possible to program a Turing machine to compute √2 to 10 decimals, but that doesn't mean you should go out and buy a Turing machine if you want to know the diagonal of a square. --RDBury (talk) 04:46, 16 October 2024 (UTC)

Speaking of that, some years ago I wrote a program to try to find a prime (any prime) by plugging in values for the variables. It ran for hours without finding a 26-tuple that works. Are there any 26-tuples known that yield a prime? Bubba73 ^{You talkin' to me?} 06:44, 16 October 2024 (UTC)

The 11 variables $b,c,d,f,i,o,r,s,t,v,w$ are each used in only one equation, and the 2 variables $h,j$ are used in just two equations, so you can try to solve for these after plugging in 2 less than the value of some prime for $k$ and nonnegative integer values for the 12 other variables. This reduces the search space from $\aleph _{0}^{26}$ to $\aleph _{0}^{12}$ :).  --Lambiam 14:50, 16 October 2024 (UTC)

Thanks, I didn't think about coming from the other end. Bubba73 ^{You talkin' to me?} 23:44, 16 October 2024 (UTC)

You can in fact go further in conquering the space. After assigning values to just the two of $a$ and $e,$ the value of $e^{3}(e+2)(a+1)^{2}+1$ needs to be a square, otherwise the equation for $\alpha _{4}$ cannot be solved and you must backtrack and try other values for $a$ and $e.$ If the value is a square, you now also have the value of $o.$ Next, assign a value to $y$ and do likewise with $\alpha _{5}$ to either backtrack or solve for $x.$ And likewise with $\ell$ and $\alpha _{8}$ to solve for $m.$ The remaining system is still formidable but less insuperable.  --Lambiam 09:01, 17 October 2024 (UTC)

Thanks, I might get back to this one day. I'd like to see an example that gives a prime. Bubba73 ^{You talkin' to me?} 02:15, 18 October 2024 (UTC)

I think I understand now. So for any given prime (k + 2), there will be some set of positive values for which the inequality is guaranteed to hold true. Got it! Amazing that you were able to isolate those variables, too. How on Earth do you do it? Touche! I am still slogging through the basic maths, lol.... Earl of Arundel (talk) 02:01, 18 October 2024 (UTC)

I used a little program to tabulate for each subset of variables in which set of equations it was used (excluding variables already listed in a smaller subset), as well as how many distinct variables were used in each equation. The things I mentioned were staring me in the face. Perhaps more elementary algebra can be applied to limit the search, but I looked no further. Considerations based on nodular arithmetic may also help.  --Lambiam 13:03, 19 October 2024 (UTC)

The section describes a prime-generating inequality. Its terms are polynomials, so this inequality is a polynomial inequality, The bracketing is not as in "[prime-generating polynomial] inequality", but as in "prime-generating [polynomial inequality]". To make the inequality actually produce primes, one has to turn the crank really hard.  --Lambiam 05:13, 16 October 2024 (UTC)

Crank the handle really hard? Ha ha, that's for sure!. If you want to go through all single digit combinations of values for the 26 variables you have 10^26 different possibilities. That'll take half a lifetime even on an exaflop supercompute and perhaps you'll get the primes 2,3,5,7. Two digits would take 10^26 longer. The Hitchikers Guide to the Galaxy's Deep Thought would have nothing on it. NadVolum (talk) 23:13, 18 October 2024 (UTC)