Wikipedia:Reference desk/Archives/Mathematics/2023 January 23

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.

January 23

Unlucky sum of three primes

Is there a number that can be written as the sum of three odd primes in exactly 13 different ways?  --Lambiam 10:46, 23 January 2023 (UTC)

If you don't find an answer here, it sounds like your question may make a good video topic for either a Numberphile, Mathologer, or Matt Parker video. Maybe you could write to them and see if they put it in the queue. --Jayron32 13:11, 23 January 2023 (UTC)

I'm pretty sure the answer is no. I ran a quick script and couldn't find any, and based on the following argument, I think that might generally suffice.

If we take some odd number $n$ and some odd prime $p_{1}\leq n-6$, then $n-p_{1}$ is an even number greater than 4 and almost certainly (cheekily assuming Goldbach's conjecture) the sum of two odd primes $p_{2},p_{3}$. Of course, we can't say anything about uniqueness of solutions if we don't establish some condition on $p_{1}$ (e.g. $n=15$ and $p_{1}=3$, $p_{2}=5,p_{3}=7$ is the same solution as $p_{1}=7$, $p_{2}=3,p_{3}=5$.) Luckily though, if we consider only $p_{1}$ between ${\frac {n}{2}}$ and $n-6$ inclusive, each $p_{1}$ gives us at least one unique solution, since it would be impossible for two of the three primes summing to $n$ to be greater than ${\frac {n}{2}}$. So the number of unique ways to have $n$ be the sum of three primes is at least the number of primes between ${\frac {n}{2}}$ and $n-6$ inclusive.

I'd have to look deeper to find any heuristics on what this might be, but I'm willing to bet that it has a growth rate that leads to the nonexistence of a number that is the sum of three odd primes in 13 different ways. GalacticShoe (talk) 21:54, 23 January 2023 (UTC)

Okay, so according to Bertrand's postulate#Erdős's theorems, "Erdős proved in 1934 that for any positive integer k, there is a natural number N such that for all n > N, there are at least k primes between n and 2n." If we consider the odd number $n$ from earlier, then since $n+1$ is even, we know that after some point, there are always at least 16 primes between ${\frac {n+1}{2}}$ and $n+1$, and removing $2$ possible primes from $n,n-2,n-4$ (at least one of them has to be divisible by $3$) yields $14$ primes from which we can construct solutions. In other words, we only have to search up to a finite point to find unlucky sums of three primes before they become impossible. But as to what that finite point is? No idea, I'd have to look further. GalacticShoe (talk) 21:59, 23 January 2023 (UTC)

Effective bounds were given by Ramanujan. It appears that (assuming Goldbach) there are at least $k$ prime triplets summing up to odd $n$ when $n>{\tfrac {1}{2}}R_{k}$, in which $R_{k}$ denotes the $k$-th Ramanujan prime. Since $75>{\tfrac {1}{2}}R_{14}={\tfrac {149}{2}},$ the search can stop quite early.  --Lambiam 23:34, 23 January 2023 (UTC)

 Solved.

13 is the smallest count which doesn't occur. In PARI/GP for sums below 10000:

m=10000; v=vector(m);
forprime(p=3,m,forprime(q=p,m-p,forprime(r=q,m-p-q,v[p+q+r]++)))
v=vecsort(v); for(n=0,100,if(!setsearch(v,n),print1(n", ")))

Output: 13, 15, 17, 19, 22, 23, 26, 31, 39, 40, 41, 43, 44, 49, 51, 52, 57, 63, 65, 66, 67, 70, 71, 78, 79, 82, 83, 84, 87, 92, 94, 96, 97, 98, 99,

PrimeHunter (talk) 19:47, 28 January 2023 (UTC)

Rule of inference vs. logical consequence

I think I understand the distinction between material conditional and logical consequence: A logically implies B iff A → B is a tautology, right? But I must be confused, because this seems the same as the relationship between material conditional and rule of inference. (The article on rule of inference even seems to equate rules of inference with entailment in this section, and our article on logical consequence seems to take entailment as a synonym for logical consequence.) Yet Hilbert systems for propositional logic make a clear distinction between an axiom, which seems in this context to be a statement that some propositional formula is a tautology, and an inference rule. What am I missing? -Amcbride (talk) 16:03, 23 January 2023 (UTC) (EDIT: Just realized that middle section of rule of inference says it's using the sequent notation, which I'm used to seeing as entailment, specifically to emphasize the distinction between axioms and rules of inference... but in my confusion, this notation just seems to blur the distinction further.)

Inference rules and tautologies are very closely related. Let's consider modus ponens: $P,P\to Q\vdash Q$. There's a corresponding tautology: $(P\wedge (P\to Q))\to Q$. In general, any rule of inference gives rise to a tautology by writing that the conjunction of the hypotheses imply the conclusion -- this is called soundness of the rules of inference. Conversely, for tautologies of the form $A\to B$, you can show $A\vdash B$ by a sequence of rules of inference -- this is completeness of the rules of inference.

An important thing to understand is that tautologies are statements in the logical language, but rules of inference are not. Rules of inference are methods of combining statements to generate new statements.

Axioms are statements, but are generally not tautologies. They are additional statements which we are asserting to be true.--2600:4040:7B33:6E00:5D8:EC09:6C4:6CA0 (talk) 17:14, 23 January 2023 (UTC)

Thanks. I think part of my confusion is that, although a tautology itself is a statement in an object language, the statement that a given tautology is indeed a tautology is a metalanguage statement. Right? It's that latter animal, the assertion that a given statement is a tautology, that I'm having trouble distinguishing from a rule of inference [EDIT: when the tautology is an implication, I mean]. (And you say axioms are not generally tautologies, but for propositional logic, they are, right?) -Amcbride (talk) 17:53, 23 January 2023 (UTC)

(edit conflict) I may not be the best person to answer this, since I, like you, have been confused by the way this is defined and discussed in the literature. Here is my try:

Given a logic (a formal system), one should distinguish between the theory $\Theta$ of the logic, formed by the sentences that can be proved as theorems using its rules of inference, and its "necessity" $\Delta$, being the set of sentences that are true in all models of the logic. Normally, one should only allow ground terms here or variables that are bound by a quantifier; otherwise the notion of a sentence being true is unclear. If the logic is sound, $\Theta \subseteq \Delta ,$ that is, all provable sentences are true in all models. If the logic is complete, the converse inclusion $\Delta \subseteq \Theta$ holds. The easiest way (IMO) to think of the material conditional (aka "material implication") is as just a formula in the formal language of the logic, assuming it has an implication connective such as $\to$, in which case it is a sentence $\sigma$ of the form $P\to Q.$ Depending on the logic and on the antecedent and consequent of $\sigma$, it may or may not be an element of $\Theta ,$ and it may or may not be an element of $\Delta .$ All four cases are possible. But if it is a member of $\Delta ,$ it gets awarded a special status, variously known as "strict implication", or "entailment", or "logical consequence". The latter term is confusing; this notion of "consequence" is in terms of the models of the logic, and is not related to its deductive system with its rules of inference. It is a semantic notion; using double turnstile notation, we can express it as $\vDash P\to Q.$  --Lambiam 17:18, 23 January 2023 (UTC)

Thank you. This gives me a lot to read. I think part of my problem may be that I don't know enough about model theory or proof theory to disentangle ideas that belong with one or the other. -Amcbride (talk) 17:59, 23 January 2023 (UTC)

You don't need to know much about model theory or proof theory, as long as you keep in mind that soundness and completeness of a formal system are different properties that both cannot be taken for granted. Being true (technically known as being a tautology, sometimes denoted "$\vDash P$ ") and being provable (denoted with a single turnstyle as "$\vdash P$ ") are different properties of a sentence. Consider a formal system whose only sentence is $\top ,$ with the understanding that we only consider standard interpretations in which this stands for the truth value “true". Then the system has only one model, and in this model $\top$ is true, so it is a tautology. If we now choose not to add any axioms or inference rules to the system, it has no theorems, so it is not only very sound but also very incomplete. Specifically, we have $\,\vDash \top$ but $\;\not \vdash \top$.  --Lambiam 22:08, 23 January 2023 (UTC)

Thank you; I think this really does help me see it. To test my understanding, in the context of a typical propositional calculus, we could write:

• "$A\land (A\to B)\to B$"

...a sentence in the object language

• "$A\land (A\to B)\to B\equiv \mathbf {T}$"

...a sentence in metalanguage, equivalent to "$A\land (A\to B)\vDash B$"

• "Modus ponens is a valid inference rule."

...a different sentence, also in metalanguage, equivalent to "$A,A\to B\vdash B$"

Do I have that right? -Amcbride (talk) 04:44, 24 January 2023 (UTC)

Just as a distinction is made between material and logical implication, logicians make a similar distinction between material and logical equivalence. Unfortunately, there is no standard notation, and the symbol "$\equiv$" is used in either of the two senses. The meaning of the second bullet is therefore not clear without context. The same applies to the use of "valid" in the third bullet. Does it mean to say that modus ponens is one of the rules of the calculus (if it isn't, a derivation using this non-existent rule does not follow the rules of the game and may be considered invalid), or is the sense that given in the article Validity (logic), in which the argument "$P$ and $Q$, therefore $R$" is only considered valid when $P,Q\vDash R$? The judgement "$A,A\to B\vdash B$" can be called a symbolic rendering of the modus ponens rule itself (see the infobox in our Modus ponens article) – although some formal systems allow one to derive the conclusion without the use of modus ponens, so this symbolic rendering is not entirely equivalent.  --Lambiam 08:00, 24 January 2023 (UTC)

I appreciate your continued help, Lambiam. In my second bullet I intended $\equiv$ to mean logical equivalence, not material. In my third bullet, I was confused, but I think I understand the distinction now. Stating "$A,A\to B\vdash B$" is equivalent to simply saying that modus ponens is a rule of the calculus, without saying whether it is valid, right? -Amcbride (talk) 17:09, 24 January 2023 (UTC)

That is correct, with the proviso that the calculus might offer some other path for deriving $B$ from $A$ and $A\to B,$ so to be very precise this statement is equivalent to saying that the theorems of the calculus, if it does not already have modus ponens as a rule, will not be affected by adding it as a rule.  --Lambiam 18:54, 24 January 2023 (UTC)

That makes sense. Thanks again. -Amcbride (talk) 19:54, 24 January 2023 (UTC)

For an alternative rule to modus ponens, see modus tollens. See also the article on sequents, which are used in sequent calculus as formal formulas, not as metalanguage statements.  --Lambiam 20:17, 24 January 2023 (UTC)