Wikipedia:Reference desk/Archives/Mathematics/2020 January 19

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 19

Closest integer solution

Given the expression

32768 + e = 168000000 / ((a + 1)(b + 1))

I'm looking for positive integer values of a and b which minimise the error e.

Is there some sort of on-line resource which solves this type of minimisation problem?

2A01:E34:EF5E:4640:DC91:D29A:9D48:BFDD (talk) 15:17, 19 January 2020 (UTC)

Oops. I realised just after posting that I can find the closest integer solution for (a+1)(b+1) directly and then look for factors. 2A01:E34:EF5E:4640:DC91:D29A:9D48:BFDD (talk) 15:41, 19 January 2020 (UTC)

continuum hypothesis and machine learning

[1][2] and (paywalled, the actual result)[3]). Any idea what this is about? They claim a result that a certain problem in machine learning (ML) is equivalent to CH. But I thought there was a theorem that CH can't affect the truth of any statements that weren't fairly far up up in AH; and (empirically) such statements don't seem to come up very often in science or applied math. The research article is paywalled and there's not enough info in the abstract or summaries for me to infer a reasonable statement of the theorem they proved. It sounds like it has to be pretty artificial and irrelevant to ML as an applied area though. Any guesses? Also, does the theorem about CH not affecting low-complexity statements have a name? Trovatore I think this is your area. Thanks! 2601:648:8202:96B0:0:0:0:DF95 (talk) 19:04, 19 January 2020 (UTC)

No arithmetical statement can be equivalent to CH over ZFC. That's because forcing cannot change the truth value of an arithmetical statement, and forcing can make CH either true or false. To put it another way, the natural numbers of L are the honest-to-God naturals, so L correctly computes the truth value of any arithmetical statement — but if G is generic for a forcing over L that makes CH false, then the naturals of L[G] are also the honest-to-God naturals, and so L[G] computes the truth value of the statement the same way.

I'm actually stating this fairly weakly. See Shoenfield absoluteness for a stronger statement.

I'm certainly not saying the claim is wrong. I do expect that, when you find out what the claim actually is, it will turn out to have been stated in a broader or more abstract context than usual in computer science. --Trovatore (talk) 03:55, 20 January 2020 (UTC)

Aha, I guess I should have said analytical hierarchy instead of arithmetical. They are probably talking about the picture as a mapping from R² to brightness levels or something like that, so their samples are sets of reals. Schoenfeld absoluteness looks like the theorem I was thinking of, so the statement they proved must be several quantifiers deep, i.e. maybe above $\Pi _{1}^{3}$ if the truth value changes when you flip CH. Do I have that right? Anyway, the claim that CH is relevant to machine learning sounds pretty bogus to me. Thanks. 2601:648:8202:96B0:0:0:0:DF95 (talk) 04:16, 20 January 2020 (UTC) Actually going even further, I thought it was empirically true that just about everything in applied math can be encoded in Peano arithmetic, i.e. most of the usual theorems of analysis can actually be written and proved arithmetically, even though they are usually written as first-order statements about reals. Is that also right? That would make CH even further "out there". 2601:648:8202:96B0:0:0:0:DF95 (talk) 04:22, 20 January 2020 (UTC)

I think you meant $\Pi _{3}^{1}$ rather than $\Pi _{1}^{3}$. That part is basically right. Shoenfield absoluteness means that $\Sigma _{2}^{1}$, and therefore also $\Pi _{2}^{1}$, statements are absolute between transitive models, and therefore $\Sigma _{3}^{1}$ statements relativize up — if they're true in the smaller transitive model, they're also true in the bigger one.

Therefore CH cannot be equivalent over ZFC to a $\Sigma _{3}^{1}$ statement (because whatever truth value CH has in your ground model, you can give it the opposite truth value in a forcing extension). So the simplest a CH-equivalent statement can be is $\Pi _{3}^{1}$ (where I'm not pinning myself down as to what exactly "simplest" means).

Actually more large cardinals give you more absoluteness, so CH can't "really" be captured by any analytical proposition. In some sense CH is the canonical $\Sigma _{1}^{2}$ statement; that is, it can be expressed by saying there is a set of reals such that blah blah blah, where blah blah blah talks about reals but not sets of reals, and CH sort of "captures" $\Sigma _{1}^{2}$-ness in a sense that I really ought to look up before saying more about it, to avoid saying something dumb.

As to the "usual theorems of analysis" being basically arithmetical, personally I wouldn't agree with that. It sounds like something out of Knuth's concrete mathematics maybe? It's an interesting program, but I don't buy that it obviates the usefulness of the reals. --Trovatore (talk) 19:49, 21 January 2020 (UTC)

Now that I think about it, even without large cardinals, a CH-equivalent statement can't be $\Pi _{3}^{1}$ either, for basically the same reason. Suppose a $\Pi _{3}^{1}$ statement σ were equivalent to CH. Then ¬σ would be $\Sigma _{3}^{1}$ and equivalent to ¬CH. But then take a transitive model M of ¬CH and force to make CH true in a generic extension M[G]. Then ¬σ is true in M but false in M[G]. But that's impossible because $\Sigma _{3}^{1}$ relativizes up.

So the simplest statement would have to be beyond both $\Sigma _{3}^{1}$ and $\Pi _{3}^{1}$. I'm not sure how far beyond.

I don't immediately see any reason CH couldn't be equivalent to, say, the disjunction of a $\Sigma _{3}^{1}$ statement and a $\Pi _{3}^{1}$ statement, over some theory that denies large cardinals, say ZFC+"0# does not exist". --Trovatore (talk)

Thanks, yeah, I got those indices reversed. Regarding analysis being arithmetical, that was something I'd heard, that I think refers to work by Gaisi Takeuti where he "develops classical analysis including complex analysis in Peano’s arithmetic",[4] but I haven't studied this. It may be similar to reverse mathematics, which develops analysis through increasingly powerful axiom sets starting with RCA0 which is a conservative extension of PA. RCA0 apparently suffices for most "applied" analysis, with the more powerful axioms being used for "soft" analysis, topology, etc. 2601:648:8202:96B0:0:0:0:4FFF (talk) 19:06, 23 January 2020 (UTC)

So the blurb for Takeuti's book (which sounds very interesting!) says that he proves that any arithmetical theorem provable in analytic number theory can be proved in PA. Now, analytic number theory is not usually thought of as an "applied" domain. Sure, there's some sense in which results about the physical world are of finite precision, and therefore can be coded by natural numbers, but this is not really the "applied" approach. What you generally do in applied math is prove theorems about infinite-precision objects such as real or complex numbers and functions on them. Then at the last step, you just round them off to finite precision and hope it works, which it usually does.

I do think I've read somewhere that Shoenfield absoluteness covers all of "hard analysis", whatever that means exactly. --Trovatore (talk) 02:36, 24 January 2020 (UTC)

The point about Takeuti's result is that if all the arithmetic statements from analytic number theory can be proved in a conservative extension of PA (presumably RCA0 mentioned above), then all the theorems of complex analysis used in them must also go through in RCA0. You might look at John Stillwell's book on reverse mathematics if you're interested in that sort of thing. I haven't seen it myself but it is supposed to be good and I've been wanting to get it. This area was User:CBM's specialty but he hasn't edited in a long while. Do you have any idea what happened to him? I haven't been around that much either. 2601:648:8202:96B0:0:0:0:4FFF (talk) 09:07, 24 January 2020 (UTC)

Hmm? No, I don't think it follows at all that the theorems of analysis must go through, just because their arithmetic consequences do. At the very least there's a huge logical gap there that you'll need to explain.

As for CBM, I think he's quit Wikipedia. I did see him very recently in person. We didn't talk much, but he confirmed that he's basically given it up. --Trovatore (talk) 17:50, 24 January 2020 (UTC)

Hmm, maybe you are right. My line of thought was 1) suppose you have a typical analytic proof where, say, you use a contour integral to prove an arithmetic sentence about prime numbers. Your proof in turn relies on the standard theorems about contour integrals, that tie in with the rest of complex analysis. 2) Takeuti's result as I heard it is basically an automated way of transforming your analytic proof into a PA proof by encoding reals as finite (or at least computable) sets of integers, 3) therefore that same transformation must also apply to the theorems you relied on, converting them to PA theorems. But you're right, there is a gap, and the reverse math article mentions that the ACA0 system (which is stronger than RCA0) is also conservative over PA for arithmetic sentences. It does look like ACA0 is strong enough to prove most of the usual theorems of analysis. The theorems mentioned under the stronger-than-ACA0 axiom systems in the reverse math articles all have more of a set theory flavor.

Thanks for the info about CBM. It looks like we also lost R.e.b. a few years ago, not good. R.e.b. had mentioned a few times that most of analysis can be done in PA with enough encoding, so that's where I got that notion, but I still haven't chased down the exact meaning. 2601:648:8202:96B0:0:0:0:4FFF (talk) 03:41, 26 January 2020 (UTC)

I looked at the paper. Here's the statement they are considering:

There is a $d\in \omega$ and a function $G:\mathbb {R} ^{d}\to [\mathbb {R} ]^{<\omega }$ such that if $P$ is any finite support probability measure on $\mathbb {R}$, then $P(G(x_{0},\dots ,x_{d-1}))>2/3$ with probability at least 2/3, where the $x_{i}$ are generated i.i.d. from $P$.

(In the vocabulary of learning theory, $G$ is the learner, and $x_{0},\dots ,x_{d}$ is the training set.)

They claim that this statement is equivalent to $\mathbf {c} <\aleph _{\omega }$.100.34.119.185 (talk) 06:21, 20 January 2020 (UTC)

Thanks! Does the notation $[\mathbb {R} ]^{<\omega }$ mean the set of all finite subsets of $\mathbb {R}$? The result seems surprising to me, but I don't have any experience in this area. 2601:648:8202:96B0:0:0:0:4FFF (talk) 19:55, 20 January 2020 (UTC)

I found what might be a preprint of the paper (Nov. 2017), arXiv:1711.05195, and will look at it. Thanks again. 2601:648:8202:96B0:0:0:0:4FFF (talk) 00:03, 21 January 2020 (UTC)

The statement looks $\Sigma _{1}^{2}$ to me, same as CH, though I wouldn't claim to be 100% sure there's not some gotcha I'm not seeing. (The map G can be coded by a set of reals.) I don't know whether ${\mathfrak {c}}<\aleph _{\omega }$ is $\Sigma _{1}^{2}$. --Trovatore (talk) 01:10, 22 January 2020 (UTC)