Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Is this product always greater than these sums?

  1. Mar 27, 2016 #1
    I've been working on a problem for a couple of days now and I wanted to see if anyone here had an idea whether this was already proven or where I could find some guidance. I feel this problem is connected to the multinomial theorem but the multinomial theorem is not really what I need . Perhaps someone on this forum knows how this problem would be named and even how to solve it. I feel like this should be easy to prove and I've proven single specific cases but I can't wrap my head around the more general case and in fact have no idea whether it's provable, proven, or even true.

    So we have a set ω containing n numbers referred to as P1, P2, P3...

    Each of these numbers is a distinct prime number greater than 4. It may or may not be relevant to the proof, but ω always contains all qualifying prime numbers up to a certain number, so it would be impossible to have missing prime numbers, and the following set would be impossible (ω = P1:3 = [5, 7, 13]). You can only have ω that include all prime numbers up to a point, such as (ω = P1:3 = [5, 7, 11]), or (ω = P1:2 = [5, 7]).

    Note that because all elements of ω are ordered and distinct, and that 5 is always present in the set, we can write them as prime gaps being added to 5 in the following way:

    P1 = P1 = 5
    P2 = P1 + PG2 = 5 + 2 = 7
    P3 = P1 + PG2 + PG3 = 5 + 2 + 4 = 11
    ...

    where PGi reads "the prime gap associated with Pi" and where the indexing of the gaps starts at P1 = 5, and PG1 = 0.

    So to recapitulate the conditions in a cleaner list:

    Conditions

    ω contains all distinct prime numbers between 4 and a given integer (condition 1)

    ω has a certain size n > 1 (condition 2)

    Due to Bertrand's postulate, note that any PGi < Pi.


    Specific formulation of the problem (this is an equivalent of the general case with m = n)

    Prove that for any given ω with number of elements n > 1, the product of all P in ω is greater than the sum of the products of all possible combinations of subsets of ω with size n - 1.

    So, for instance, for n = 2, prove that:

    P1P2 > P1 + P2

    or, for another instance with n = 4, prove that:

    P1P2P3P4 > P1P2P3 + P1P2P4 + P1P3P4 + P2P3P4

    General formulation of the problem

    Prove that for any given ω with number of elements n > 1, given any chosen integer 1 > m ≤ n, the sum of the products of all possible combinations of subsets of ω with size m is greater than the sum of the products of all possible combinations of subsets of ω with size m - 1. So, for instance:

    for n = 4 and m = 3,

    P1P2P3 + P1P2P4 + P1P3P4 + P2P3P4 > P1P2 + P1P3 + P1P4 + P2P3 + P2P4 + P3P4

    or for n = 5 and m = 4,

    P1P2P3P4 + P1P2P3P5 + P1P2P4P5 + P1P3P4P5 + P2P3P4P5 > P1P2P3 + P1P2P4 + P1P2P5 + P1P3P4 + P1P3P5 + P1P4P5 + P2P3P4 + P2P3P5 + P2P4P5 + P3P4P5

    Example proof

    I've had success handling single cases by expressing all primes as being an addition of prime gaps with 5, for instance:

    Proof for m = 2 and n = 2

    Prove that P1P2 > P1 + P2

    We know that P2 = P1 + PG2, therefore:

    P1(P1 + PG2) > P1 + P1 + PG2

    P12 + P1PG2 > 2P1 + PG2

    We may label these 4 terms as term 1, 2, 3 and 4. It is easy to see that term 1 is greater than term 3, because P1 > 2 (condition 1). It is also easy to see that term 2 is greater than term 4, because P1 > 1 (condition 1).

    Therefore the left side has to be greater than the right side.

    Help needed!

    I'd love to see if anyone has some guidance to provide on proving the general case. It feels like this is strongly related to the Pascal triangle and multinomial theorem but I have difficulties finding where to start.
     
  2. jcsd
  3. Mar 27, 2016 #2
    The line "Due to Bertrand's postulate, note that any PGi < Pi" should have read:

    Due to Bertrand's postulate, note that any PGi < Pi-1
     
  4. Mar 27, 2016 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The special case is wrong. Divide both sides by the product, and it is claiming 1 > 1/5 + 1/7 + 1/11 + ... up to some prime number P. The sum of inverse prime numbers diverges, so there are prime numbers where this inequality is violated.

    General case:
    There are not many integers smaller than 1. Do you mean 1<m?

    I don't think prime gaps are useful here.
     
  5. Mar 27, 2016 #4
    You're totally right, I mean 1 < m . In the case where the statement is false, I'm interested in identifying for which m and n it would be true.
     
  6. Mar 27, 2016 #5
    I have checked and indeed 109 is the prime at which the 1 > ... inequality is violated. Thank you very much for pointing that out, I guess I now have to go back to the workbench and see what reformulation I could find and what kind of boundaries I would put on m and n.
     
  7. Mar 27, 2016 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It is not valid for m=n as established, and it is valid for no m. Proof:

    Let S(p1,p2) be the sum of inverse primes from p1 to p2 inclusive, e.g. S(5,11)=1/5+1/7+1/11.
    Let pn be the nth prime larger than 4, e.g. p1=5.
    Let A(n,m) be the sum of all possible products of m distinct primes out of the first n primes pi, divided by the product of those n primes, e.g.
    A(3,2)=(5*7+5*11+7*11)/(5*7*11)=1/5+1/7+1/11=S(5,11)
    A(3,1)=(5+7+11)/(5*7*11)=1/(5*7)+1/(5*11)+1/(7*11)=1/5*S(7,11)+1/7*S(11,11)

    The case m=n-1 is then the claim A(n,n-1)>A(n,n-2).
    $$A(n,n-1)=S(p_1,p_n)$$
    $$A(n,n-2) = \sum_{i=1}^{i=n-1} \frac{1}{p_i} S(p_{i+1},p_n)$$

    Divide the set of primes into sets with a reciprocal sum of more than 1, e.g. 1/5+1/7+1/11+...+1/109 > 1 leads to the first block, 1/(113) + 1/... +1/whatever > 1 leads to the primes of the second block and so on. Let's call pa,b the b'th prime of block a.
    As all the blocks end with primes above 10, we also know that the sum of inverse primes in each block is smaller than 1.1.

    For A(n,n-2) we form products of pairs of inverse primes. Among them, if n is sufficiently large, we'll find blocks like $$\frac{1}{p_{1,1}p_{2,1}} + \frac{1}{p_{1,1}p_{2,2}}+ \dots + \frac{1}{p_{1,2}p_{2,1}} + \frac{1}{p_{1,2}p_{2,2}}+ \dots \\= \frac{1}{p_{1,1}} \sum_{i=1}^{i_{max}} \frac{1}{p_{2,i}} + \frac{1}{p_{1,2}} \sum_{i=1}^{i_{max}} \frac{1}{p_{2,i}} \\> \sum_{j=1}^{j_{max}} \frac{1}{p_{1,j}} > 1$$
    In other words, the products coming from such a block combination add up to more than 1.

    Let's consider n such that the primes cover the first 4 blocks. Then A(n,n-1)<4.4, but A(n,n-2) >6 because we have the block combinations (1,2), (1,3), (1,4), (2,3), (2,4) and (3,4).

    => it is not valid for m=n-1 either.

    Using similar arguments, you can show that it is valid for no m.
     
  8. Mar 27, 2016 #7
    Brilliant! You are so much better than me it is both helpful and shameful at the same time. This means I have to reformulate my statement of the problem. I'm quite convinced that what I'm after is true, but I haven't been completely honest in my original post. For your curiosity, and if you are willing to grace me with more of your help, what I was really after is:

    Prove that for any n, The following additions/subtraction leads to a result greater than zero:

    (first line is positive with m = n and each term contains n Ps)
    + P1P2...Pn

    (second line is negative with m = n-1 and each term contains n-1 Ps)
    - P1P2...Pn-1 - P1P2...Pn - ...

    (third line is positive but multiplied by 2 with m = n-2 and each term contains n-2 Ps)
    + 2(P1P2...Pn-2 + P1P2...Pn-1 + P1P2...Pn + ...)

    (fourth line is negative but multiplied by 2 with m = n-3 and each term contains n-3 Ps)
    - 2(P1P2...Pn-3 + P1P2...Pn-2 + P1P2...Pn-1 + P1P2...Pn + ...)

    (each line after that simply alternates between - and + and is also multiplied by 2 all the time while m diminishes 1 by 1)
    ...

    (second to last line negative, with m = 2 and each term containing 2 Ps, also multipled by 2)
    + 2 (P1P2 + P1P3 + ...)

    (last line m = 1, each term containing 1 P, also multiplied by 2)
    - 2 (P1 + P2 + ...)

    (and very last line)
    + 2

    The reason I formulated the problem differently in the original post is that I was convinced that the - lines were always smaller than the + lines!
     
  9. Mar 27, 2016 #8
    So I've used your approach empirically (that is, divide all lines by all primes in the set) and I have moved the "1" that resulted to the left side of the equation so we have:

    1 > 1/P1 + 1/P2 + 1/P3 ...
    - 2/(P1P2) - 2/(P1P3) ...
    + 2/(P1P2P3) ...
    - 2/(P1P2P3P4) ...

    and I just wanted to show you the results empirically, for the first 21 primes. It seems like it will never reach 1 unless something surprising happens. So the question is whether we can prove that it's converging below one, or that it is not converging but that it is constantly decreasing and never going back toward 1. The Y axis shows the sum of the right hand side of the inequality.

    CuURQFL.png
     
  10. Mar 27, 2016 #9
    I'm attaching here the Matlab code used to generate the previous figure in case someone wants to reproduce the empirical algorithm. It's currently going very slow because I use the function nchoosek, there is probably much faster available.

    Code (Text):
    n = 87;

    SumsData = [];
    PrimesOriginal = 5:n;
    PrimesOriginal = PrimesOriginal(isprime(PrimesOriginal));

    for i=2:length(PrimesOriginal),
        i,
        Primes = PrimesOriginal(1:i);
        Sum = 0;
        OneOrTwo = 1;
        Sign = -1;
        for z=1:length(Primes),
            Sign = Sign*-1;
            if z == 2,
                OneOrTwo = 2;
            end
            Temp = nchoosek(Primes,z);
            for j=1:size(Temp,1),
                Sum = Sum + Sign*(OneOrTwo/(prod(Temp(j,:))));
            end
        end
        SumsData(i) = Sum;
    end

    figure;plot(SumsData);
     
  11. Mar 27, 2016 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Where does the new expression come from?
    If you stop after 4 elements, it will go to negative infinity. If you always consider all those terms up to n as the code suggests, the question becomes more interesting.
     
  12. Mar 27, 2016 #11
    Definitely, the illustration of the case of 4 is simply because I have a hard time expressing it in general terms but yes, the system grows with n and I certainly do not limit the question to 4 lines. The question I ask is whether or not SumsData(i) will remain below 1 at all times as i goes to infinity. And a cleaner, more general representation of the inequality would be:

    1 > 1/P1 + 1/P2 ... + 1/Pn
    - 2/(P1P2) - 2/(P1P3) ... - 2/(Pn-1Pn)
    ...
    ...
    - 2/(P1P2...Pn-1Pn)

    (note that for odd number of lines the line finishes with a - whereas for even number of lines it would finish with a +)

    This formulation of the problem comes from the actual problem as I am facing it. This is a missing piece of the puzzle in imposing a boundary on prime densities of certain types of primes for me which is needed as part of an on-going attempt to prove the Goldbach conjecture.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted