Tagged: proof Toggle Comment Threads | Keyboard Shortcuts

  • Joseph Nebus 6:00 pm on Tuesday, 21 February, 2017 Permalink | Reply
    Tags: automated proofs, , , , proof   

    One Way To Get Your Own Theorem 


    While doing some research to better grouse about Ken Keeler’s Futurama theorem I ran across an amusing site I hadn’t known about. It is Theory Mine, a site that allows you to hire — and name — a genuine, mathematically sound theorem. The spirit of the thing is akin to that scam in which you “name” a star. But this is more legitimate in that, you know, it’s got any legitimacy. For this, you’re buying naming rights from someone who has any rights to sell. By convention the discoverer of a theorem can name it whatever she wishes, and there’s one chance in ten that anyone else will use the name.

    I haven’t used it. I’ve made my own theorems, thanks, and could put them on a coffee mug or t-shirt if I wished to make a particularly boring t-shirt. But I’m delighted by the scheme. They don’t have a team of freelance mathematicians whipping up stuff and hoping it isn’t already known. Not for the kinds of prices they charge. This should inspire the question: well, where do the theorems come from?

    The scheme uses an automated reasoning system. I don’t know the details of how it works, but I can think of a system by which this might work. It goes back to the Crisis of Foundations, the time in the late 19th/early 20th century when logicians got very worried that we were still letting physical intuitions and unstated assumptions stay in our mathematics. One solution: turn everything into symbols, icons with no connotations. The axioms of mathematics become a couple basic symbols. The laws of logical deduction become things we can do with the symbols, converting one line of symbols into a related other line. Every line we get is a theorem. And we know it’s correct. To write out the theorem in this scheme is to write out its proof, and to feel like you’re touching some deep magic. And there’s no human frailties in the system, besides the thrill of reeling off True Names like that.

    You may not be sure what this works like. It may help to compare it to a slightly-fun number coding scheme. I mean the one where you start with a number, like, ‘1’. Then you write down how many times and which digit appears. There’s a single ‘1’ in that string, so you would write down ’11’. And repeat: In ’11’ there’s a sequence of two ‘1’s, so you would write down ’21’. And repeat: there’s a single ‘2’ and a single ‘1’, so you then write down ‘1211’. And again: there’s a single ‘1’, a single ‘2’, and then a double ‘1’, so you next write ‘111221’. And so on until you get bored or die.

    When we do this for mathematics we start with a couple different basic units. And we also start with several things we may do at most symbols. So there’s rarely a single line that follows from the previous. There’s an ever-expanding tree of known truths. This may stave off boredom but I make no promises about death.

    The result of this is pages and pages that look like Ancient High Martian. I don’t feel the thrill of doing this. Some people do, though. And as recreational mathematics goes I suppose it’s at least as good as sudoku. Anyway, this kind of project, rewarding indefatigability and thoroughness, is perfect for automation anyway. Let the computer work out all the things we can prove are true.

    If I’m reading Theory Mine’s description correctly they seem to be doing something roughly like this. If they’re not, well, you go ahead and make your own rival service using my paragraphs as your system. All I ask is one penny for every use of L’Hôpital’s Rule, a theorem named for Guillaume de l’Hôpital and discovered by Johann Bernoulli. (I have heard that Bernoulli was paid for his work, but I do not know that’s true. I have now explained why, if we suppose that to be true, my prior sentence is a very funny joke and you should at minimum chuckle.)

    This should inspire the question: what do we need mathematicians for, then? It’s for the same reason we need writers, when it would be possible to automate the composing of sentences that satisfy the rules of English grammar. I mean if there were rules to English grammar. That we can identify a theorem that’s true does not mean it has even the slightest interest to anyone, ever. There’s much more that could be known than that we could ever care about.

    You can see this in Theory Mine’s example of Quentin’s Theorem. Quentin’s Theorem is about an operation you can do on a set whose elements consist of the non-negative whole numbers with a separate value, which they call color, attached. You can add these colored-numbers together according to some particular rules about how the values and the colors add. The order of this addition normally matters: blue two plus green three isn’t the same as green three plus blue two. Quentin’s Theorem finds cases where, if you add enough colored-numbers together, the order doesn’t matter. I know. I am also staggered by how useful this fact promises to be.

    Yeah, maybe there is some use. I don’t know what it is. If anyone’s going to find the use it’ll be a mathematician. Or a physicist who’s found some bizarre quark properties she wants to codify. Anyway, if what you’re interested in is “what can you do to make a vertical column stable?” then the automatic proof generator isn’t helping you at all. Not without a lot of work put in to guiding it. So we can skip the hard work of finding and proving theorems, if we can do the hard work of figuring out where to look for these theorems instead. Always the way.

    You also may wonder how we know the computer is doing its work right. It’s possible to write software that is logically proven to be correct. That is, the software can’t produce anything but the designed behavior. We don’t usually write software this way. It’s harder to write, because you have to actually design your software’s behavior. And we can get away without doing it. Usually there’s some human overseeing the results who can say what to do if the software seems to be going wrong. Advocates of logically-proven software point out that we’re getting more software, often passing results on to other programs. This can turn a bug in one program into a bug in the whole world faster than a responsible human can say, “I dunno. Did you try turning it off and on again?” I’d like to think we could get more logically-proven software. But I also fear I couldn’t write software that sound and, you know, mathematics blogging isn’t earning me enough to eat on.

    Also, yes, even proven software will malfunction if the hardware the computer’s on malfunctions. That’s rare, but does happen. Fortunately, it’s possible to automate the checking of a proof, and that’s easier to do than creating a proof in the first place. We just have to prove we have the proof-checker working. Certainty would be a nice thing if we ever got it, I suppose.

     
    • mathtuition88 5:01 am on Wednesday, 22 February, 2017 Permalink | Reply

      Computers are getting more amazing!

      Like

      • Joseph Nebus 4:19 pm on Saturday, 25 February, 2017 Permalink | Reply

        They are astounding, which makes it only the more baffling that we can’t get iTunes to reliably download new episodes of a podcast we’re subscribed to and listen to every week.

        Liked by 1 person

    • Henry Game 9:40 am on Wednesday, 22 February, 2017 Permalink | Reply

      One day I’d like you to explain the magic of numbers, vortex maths etc to me. I am interested in numerology, ancient geography, Metatron’s cube and all that, but, for some reason, I have never studied maths.
      Maybe you could inspire me and advise me where to start?
      I thoroughly enjoy your posts, when I come across them, but half the time I am blown away. 😂

      Liked by 1 person

      • Joseph Nebus 4:27 pm on Saturday, 25 February, 2017 Permalink | Reply

        Well, hm. I’m not sure about literal magic of numbers, as in numerology and the like. For what’s wonderful about mathematics … I’m still not perfectly sure. I think I’d give a try of Courant and Robbins’s What Is Mathematics?, originally published in 1940 but still in print and updated, and your library (or university library) will have copies. It’s a little survey of a lot of the fields of mathematics. And it’s mostly episodic, so if one section isn’t doing anything for you it’s fine to skip to the next, or just to pick a section arbitrarily and see what’s going on there.

        And I’m glad you enjoy stuff around here, but if you do get stuck on something please say so! It’s very hard for me to guess what people don’t know, and there’s usually a good post to be made in explaining why something confused someone.

        Liked by 1 person

      • mathtuition88 4:34 pm on Saturday, 25 February, 2017 Permalink | Reply

        I just checked out metatron’s cube, looks really cool.

        Like

  • Joseph Nebus 3:00 pm on Tuesday, 14 June, 2016 Permalink | Reply
    Tags: , , , , , proof   

    What’s The Shortest Proof I’ve Done? 


    I didn’t figure to have a bookend for last week’s “What’s The Longest Proof I’ve Done? question. I don’t keep track of these things, after all. And the length of a proof must be a fluid concept. If I show something is a direct consequence of a previous theorem, is the proof’s length the two lines of new material? Or is it all the proof of the previous theorem plus two new lines?

    I would think the shortest proof I’d done was showing that the logarithm of 1 is zero. This would be starting from the definition of the natural logarithm of a number x as the definite integral of 1/t on the interval from 1 to x. But that requires a bunch of analysis to support the proof. And the Intermediate Value Theorem. Does that stuff count? Why or why not?

    But this happened to cross my desk: The Shortest-Known Paper Published in a Serious Math Journal: Two Succinct Sentences, an essay by Dan Colman. It reprints a paper by L J Lander and T R Parkin which appeared in the Bulletin of the American Mathematical Society in 1966.

    It’s about Euler’s Sums of Powers Conjecture. This is a spinoff of Fermat’s Last Theorem. Leonhard Euler observed that you need at least two whole numbers so that their squares add up to a square. And you need three cubes of whole numbers to add up to the cube of a whole number. Euler speculated you needed four whole numbers so that their fourth powers add up to a fourth power, five whole numbers so that their fifth powers add up to a fifth power, and so on.

    And it’s not so. Lander and Parkin found that this conjecture is false. They did it the new old-fashioned way: they set a computer to test cases. And they found four whole numbers whose fifth powers add up to a fifth power. So the quite short paper answers a long-standing question, and would be hard to beat for accessibility.

    There is another famous short proof sometimes credited as the most wordless mathematical presentation. Frank Nelson Cole gave it on the 31st of October, 1903. It was about the Mersenne number 267-1, or in human notation, 147,573,952,589,676,412,927. It was already known the number wasn’t prime. (People wondered because numbers of the form 2n-1 often lead us to perfect numbers. And those are interesting.) But nobody knew which factors it was. Cole gave his talk by going up to the board, working out 267-1, and then moving to the other side of the board. There he wrote out 193,707,721 × 761,838,257,287, and showed what that was. Then, per legend, he sat down without ever saying a word, and took in the standing ovation.

    I don’t want to cast aspersions on a great story like that. But mathematics is full of great stories that aren’t quite so. And I notice that one of Cole’s doctoral students was Eric Temple Bell. Bell gave us a great many tales of mathematics history that are grand and great stories that just weren’t so. So I want it noted that I don’t know where we get this story from, or how it may have changed in the retellings. But Cole’s proof is correct, at least according to Octave.

    So not every proof is too long to fit in the universe. But then I notice that Mathworld’s page regarding the Euler Sum of Powers Conjecture doesn’t cite the 1966 paper. It cites instead Lander and Parkin’s “A Counterexample to Euler’s Sum of Powers Conjecture” from Mathematics of Computation volume 21, number 97, of 1967. There the paper has grown to three pages, although it’s only a couple paragraphs of one page and three lines of citation on the third. It’s not so easy to read either, but it does explain how they set about searching for counterexamples. But it may give you some better idea of how numerical mathematicians find things.

     
  • Joseph Nebus 3:00 pm on Tuesday, 7 June, 2016 Permalink | Reply
    Tags: , , , proof,   

    What’s The Longest Proof I’ve Done? 


    You know what’s a question I’m surprised I don’t get asked? I mean in the context of being a person with an advanced mathematics degree. I don’t get asked what’s the longest proof I’ve ever done. Either just reading to understand, or proving for myself. Maybe people are too intimidated by the idea of advanced mathematics to try asking such things. Maybe they’re afraid I’d bury them under a mountain of technical details. But I’d imagine musicians get asked what the hardest or the longest piece they’ve memorized is. I’m sure artists get asked what’s the painting (or sculpture, or whatnot) they’ve worked on the longest was.

    It’s just as well nobody’s asked. I’m not sure what the longest proof I’ve done, or gone through, would even be. Some of it is because there’s an inherent arbitrariness to the concept of “a proof”. Proofs are arguments, and they’re almost always made up of many smaller pieces. The advantage of making these small pieces is that small proofs are usually easier to understand. We can then assemble the conclusions of many small proofs to make one large proof. But then how long was the large proof? Does it contain all the little proofs that go into it?

    And, truth be told, I didn’t think to pay attention to how long any given proof was. If I had to guess I would think the longest proof I’d done, just learned, would be from a grad school course in ordinary differential equations. This is the way we study systems in which how things are changing depends on what things are now. These often match physical, dynamic, systems very well. I remember in the class spending several two-hour sessions trying to get through a major statement in a field called Kolmogorov-Arnold-Moser Theory. This is a major statement about dynamical systems being perturbed, given a little shove. And it describes what conditions make the little shove really change the way the whole system behaves.

    What I’m getting to is that there appears to be a new world’s record-holder for the Longest Actually Completed Proof. It’s about a problem I never heard of before but that’s apparently been open since the 1980s. It’s known as the Boolean Pythagorean Triples problem. The MathsByAGirl blog has an essay about it, and gives some idea of its awesome size. It’s about 200 terabytes of text. As you might imagine, it’s a proof by exhaustion. That is, it divides up a problem into many separate cases, and tries out all the cases. That’s a legitimate approach. It tends to produce proofs that are long and easy to verify, at least at each particular case. They might not be insightful, that is, they might not suggest new stuff to do, but they work. (And I don’t know that this proof doesn’t suggest new stuff to do. I haven’t read it, for good reason. It’s well outside my specialty.)

    But proofs can be even bigger. John Carlos Baez published a while back an essay, “Insanely Long Proofs”. And that’s awe-inspiring. Baez is able to provide theorems which we know to be true. You’ll be able to understand what they conclude, too. And in the logic system applicable to them, their proofs would be so long that the entire universe isn’t big enough just to write down the number of symbols needed to complete the proof. Let me say that again. It’s not that writing out the proof would take more than all the space in the universe. It’s that writing out how long the proof would be, written out would take more than all the space in the universe.

    So you should ask, then how do we know it’s true? Baez explains.

     
    • MJ Howard 3:21 pm on Tuesday, 7 June, 2016 Permalink | Reply

      I think part of the problem is that, in general, non-mathematicians don’t have much of a concept of what working mathematicians actually do. Most of the work I do that I think of as Mathematics consists of specific applications and isn’t terribly concerned with proof as such.

      That said, the most time I spent working on a proof was as an undergrad. It was a plane tiling problem involving constraints on the dimensions of the plane. I spent about a week and a half on it and only managed to prove sufficiency.

      Liked by 1 person

      • Joseph Nebus 3:08 am on Saturday, 11 June, 2016 Permalink | Reply

        You’re right. It might also be that people don’t think much about what mathematicians do all day. I’m not perfectly clear on it myself, I must admit. But when I was a real working mathematician most of my research was really numerical simulations and experiments. There were a couple of little cases where I needed to prove something, but it was all in the service of either saying why my numerical experiments should work, or why a surprising result I’d found experimentally actually made sense after all.

        My biggest work in actually coming up with proofs might have been in a real analysis course I took as a grad student. I’d had a lovely open-ended assignment and kept chaining together little proofs about one problem to build a notebook of stuff. This was all proofs about logarithms and exponentials, so none of the results were anything remotely new or surprising, but it was really satisfying to get underneath some computation rules and work them out.

        Like

    • Amie 10:26 pm on Tuesday, 7 June, 2016 Permalink | Reply

      I’m more likely to be asked ‘what is the longest equation that I’ve solved’? :)

      Related to what MJ said, when I interview high-school students for undergraduate maths scholarships, I ask them what is the longest they have ever spent solving a problem. The answer is usually 15 minutes. Occasionally someone says overnight. That gives us one clue as to what non-mathematicians (albeit maths students) think it means to be good at maths and how mathematicians work (that is, solve problems relatively quickly and move on). To be fair, I don’t expect these students to answer any differently because they respond based on (1) their experience and (2) what they think we want to hear. But it is illuminating.

      I’d never heard of the Boolean Pythagorean Triples problem until earlier this week, either. I love that there are easy to understand maths ideas that I’ve never heard of. No idea how the proof works either ;).

      Liked by 1 person

      • Joseph Nebus 3:15 am on Saturday, 11 June, 2016 Permalink | Reply

        Longest equation that I’ve solved … hm. Well, if it’s the equation I spent the longest time in solving that’s got to be something in the inviscid fluid flow that made up a lot of my thesis. The physically longest equation I don’t know. I remember shortly after starting into high school algebra at all trying to think of the hardest possible equation. Given that all I really had to work with was polynomials my first guess was just something with a bunch of variables all raised to high powers. But I also worked out that this was a boring equation. Never did work out what would be both complicated and interesting at once.

        I wonder how long non-mathematicians expect gets spent on leads that ultimately go nowhere, before a workable approach to the problem is worked out. Or if not nowhere then at least go into directions that don’t work without a lot of re-thinking and re-casting. There is a desire to show how to get right answers efficiently, for which people can’t be blamed. But the system of learning how to think of ways to get answers probably needs false starts and long periods of pondering that feel like they don’t get anywhere.

        Liked by 1 person

    • mathsbyagirl 7:54 am on Saturday, 11 June, 2016 Permalink | Reply

      I must say, I love your style of writing!

      Like

  • Joseph Nebus 3:00 pm on Wednesday, 20 April, 2016 Permalink | Reply
    Tags: , boredom, , , , proof,   

    A Leap Day 2016 Mathematics A To Z: Wlog 


    Wait for it.

    Wlog.

    I’d like to say a good word for boredom. It needs the good words. The emotional state has an appalling reputation. We think it’s the sad state someone’s in when they can’t find anything interesting. It’s not. It’s the state in which we are so desperate for engagement that anything is interesting enough.

    And that isn’t a bad thing! Finding something interesting enough is a precursor to noticing something curious. And curiosity is a precursor to discovery. And discovery is a precursor to seeing a fuller richness of the world.

    Think of being stuck in a waiting room, deprived of reading materials or a phone to play with or much of anything to do. But there is a clock. Your classic analog-face clock. Its long minute hand sweeps out the full 360 degrees of the circle once every hour, 24 times a day. Its short hour hand sweeps out that same arc every twelve hours, only twice a day. Why is the big unit of time marked with the short hand? Good question, I don’t know. Probably, ultimately, because it changes so much less than the minute hand that it doesn’t need the attention of length drawn to it.

    But let our waiting mathematician get a little more bored, and think more about the clock. The hour and minute hand must sometimes point in the same direction. They do at 12:00 by the clock, for example. And they will at … a little bit past 1:00, and a little more past 2:00, and a good while after 9:00, and so on. How many times during the day will they point the same direction?

    Well, one easy way to do this is to work out how long it takes the hands, once they’ve met, to meet up again. Presumably we don’t want to wait the whole hour-and-some-more-time for it. But how long is that? Well, we know the hands start out pointing the same direction at 12:00. The first time after that will be after 1:00. At exactly 1:00 the hour hand is 30 degrees clockwise of the minute hand. The minute hand will need five minutes to catch up to that. In those five minutes the hour hand will have moved another 2.5 degrees clockwise. The minute hand needs about four-tenths of a minute to catch up to that. In that time the hour hand moves — OK, we’re starting to see why Zeno was not an idiot. He never was.

    But we have this roughly worked out. It’s about one hour, five and a half minutes between one time the hands meet and the next. In the course of twelve hours there’ll be time for them to meet up … oh, of course, eleven times. Over the course of the day they’ll meet up 22 times and we can get into a fight over whether midnight counts as part of today, tomorrow, or both days, or neither. (The answer: pretend the day starts at 12:01.)

    Hold on, though. How do we know that the time between the hands meeting up at 12:00 and the one at about 1:05 is the same as the time between the hands meeting up near 1:05 and the next one, sometime a little after 2:10? Or between that one and the one at a little past 3:15? What grounds do we have for saying this one interval is a fair representation of them all?

    We can argue that it should be fairly enough. Imagine that all the markings were washed off the clock. It’s just two hands sweeping around in circles, one relatively fast, one relatively slow, forever. Give the clockface a spin. When the hands come together again rotate the clock so those two hands are vertical, the “12:00” position. Is this actually 12:00? … Well, we’ve got a one-in-eleven chance it is. It might be a little past 1:05; it might be that time something past 6:30. The movement of the clock hands gives no hint what time it really is.

    And that is why we’re justified taking this one interval as representative of them all. The rate at which the hands move, relative to each other, doesn’t depend on what the clock face behind it says. The rate is, if the clock isn’t broken, always the same. So we can use information about one special case that happens to be easy to work out to handle all the cases.

    That’s the mathematics term for this essay. We can study the one specific case without loss of generality, or as it’s inevitably abbreviated, wlog. This is the trick of studying something possibly complicated, possibly abstract, by looking for a representative case. That representative case may tell us everything we need to know, at least about this particular problem. Generality means what you might figure from the ordinary English meaning of it: it means this answer holds in general, as opposed to in this specific instance.

    Some thought has to go in to choosing the representative case. We have to pick something that doesn’t, somehow, miss out on a class of problems we would want to solve. We mustn’t lose the generality. And it’s an easy mistake to make, especially as a mathematics student first venturing into more abstract waters. I remember coming up against that often when trying to prove properties of infinitely long series. It’s so hard to reason something about a bunch of numbers whose identities I have no idea about; why can’t I just use the sequence, oh, 1/1, 1/2, 1/3, 1/4, et cetera and let that be good enough? Maybe 1/1, 1/4, 1/9, 1/16, et cetera for a second test, just in case? It’s because it takes time to learn how to safely handle infinities.

    It’s still worth doing. Few of us are good at manipulating things in the abstract. We have to spend more mental energy imagining the thing rather than asking the questions we want of it. Reducing that abstraction — even if it’s just a little bit, changing, say, from “an infinitely-differentiable function” to “a polynomial of high enough degree” — can rescue us. We can try out things we’re confident we understand, and derive from it things we don’t know.

    I can’t say that a bored person observing a clock would deduce all this. Parts of it, certainly. Maybe all, if she thought long enough. I believe it’s worth noticing and thinking of these kinds of things. And it’s why I believe it’s fine to be bored sometimes.

     
    • howardat58 3:33 pm on Wednesday, 20 April, 2016 Permalink | Reply

      Your point about how mathematicians think is so vital and so overlooked in the teaching of math in schools. Even the question “Is it true in a special case?” is a question rarely asked.

      Liked by 1 person

      • Joseph Nebus 2:13 am on Friday, 22 April, 2016 Permalink | Reply

        Well, thank you. While writing this I did get to thinking about how we find things that can be picked out without loss of generality, versus actually losing generality. And I didn’t think of a good example of losing generality, partly because I’m writing these much closer to deadline than I imagined and partly because I thought I was running long as it was.

        I might put a follow-up post on about how to pick examples, though.

        Liked by 2 people

  • Joseph Nebus 3:00 pm on Monday, 14 March, 2016 Permalink | Reply
    Tags: , formal language, , , , , proof   

    A Leap Day 2016 Mathematics A To Z: Grammar 


    My next entry for this A To Z was another request, this one from Jacob Kanev, who doesn’t seem to have a WordPress or other blog. (If I’m mistaken, please, let me know.) Kanev’s given me several requests, some of them quite challenging. Some too challenging: I have to step back from describing “both context sensitive and not” kinds of grammar just now. I hope all will forgive me if I just introduce the base idea.

    Grammar.

    One of the ideals humans hold when writing a mathematical proof is to crush all humanity from the proof. It’s nothing personal. It reflects a desire to be certain we have proved things without letting any unstated assumptions or unnoticed biases interfering. The 19th century was a lousy century for mathematicians and their intuitions. Many ideas that seemed clear enough turned out to be paradoxical. It’s natural to want to not make those mistakes again. We can succeed.

    We can do this by stripping out everything but the essentials. We can even do away with words. After all, if I say something is a “square”, that suggests I mean what we mean by “square” in English. Our mathematics might not have proved all the square-ness of the thing. And so we reduce the universe to symbols. Letters will do as symbols, if we want to be kind to our typesetters. We do want to be kind now that, thanks to LaTeX, we do our own typesetting.

    This is called building a “formal language”. The “formal” here means “relating to the form” rather than “the way you address people when you can’t just say `heya, gang’.” A formal language has two important components. One is the symbols that can be operated on. The other is the operations you can do on the symbols.

    If we’ve set it all up correctly then we get something wonderful. We have “statements”. They’re strings of the various symbols. Some of the statements are axioms; they’re assumed to be true without proof. We can turn a statement into another one by using a statement we have and one of the operations. If the operation requires, we can add in something else we already know to be true. Something we’ve already proven.

    Any statement we build this way — starting from an axiom and building with the valid operations — is a new and true statement. It’s a theorem. The proof of the theorem? It’s the full sequence of symbols and operations that we’ve built. The line between advanced mathematics and magic is blurred. To give a theorem its full name is to give its proof. (And now you understand why the biographies of many of the pioneering logicians of the late 19th and early 20th centuries include a period of fascination with the Kabbalah and other forms of occult or gnostic mysticism.)

    A grammar is what’s required to describe a language like this. It’s defined to be a quartet of properties. The first property is the collection of symbols that can’t be the end of a statement. These are called nonterminal symbols. The second property is the collection of symbols that can end a statement. These are called terminal symbols. (You see why we want to have those as separate lists.) The third property is the collection of rules that let you build new statements from old. The fourth property is the collection of things we take to be true to start. We only have finitely many options for each of these, at least for your typical grammar. I imagine someone has experimented with infinite grammars. But that hasn’t got to be enough of a research field people have to pay attention to them. Not yet, anyway.

    Now it’s reasonable to ask if we need mathematicians at all. If building up theorems is just a matter of applying the finitely many rules of inference on finitely many collections of symbols, finitely many times over, then what about this can’t be done by computer? And done better by a computer, since a computer doesn’t need coffee, or bathroom breaks an hour later, or the hope of moving to a tenure-track position?

    Well, we do need mathematicians. I don’t say that just because I hope someone will give me money in exchange for doing mathematics. It’s because setting up a computer to just grind out every possible theorem will never turn up what you want to know now. There are several reasons for this.

    Here’s a way to see why. It’s drawn from Douglas Hofstadter’s Gödel, Escher, Bach, a copy of which you can find in any college dorm room or student organization office. At least you could back when I was an undergraduate. I don’t know what the kids today use.

    Anyway, this scheme has three nonterminal symbols: I, M, and U. As a terminal symbol … oh, let’s just use the space at the end of a string. That way everything looks like words. We will include a couple variables, lowercase letters like x and y and z. They stand for any string of nonterminal symbols. They’re falsework. They help us get work done, but must not appear in our final result.

    There’s four rules of inference. The first: if xI is valid, then so is xIM. The second: if Mx is valid, then so is Mxx. The third: if MxIIIy is valid, then so is MxUy. The fourth: if MxUUy is valid, then so is Mxy.

    We have one axiom, assumed without proof to be true: MI.

    So let’s putter around some. MI is true. So by the second rule, so is MII. That’s a theorem. And since MII is true, by the second rule again, so is MIIII. That’s another theorem. Since MIIII is true, by the first rule, so is MIIIIM. We’ve got another theorem already. Since MIIIIM is true, by the third rule, so is MIUM. We’ve got another theorem. For that matter, since MIIIIM is true, again by the third rule, so is MUIM. Would you like MIUMIUM? That’s waiting there to be proved too.

    And that will do. First question: what does any of this even mean? Nobody cares about whether MIUMIUM is a theorem in this system. Nobody cares about figuring out whether MUIUMUIUI might be a theorem. We care about questions like “what’s the smallest odd perfect number?” or “how many equally-strong vortices can be placed in a ring without the system becoming unstable?” With everything reduced to symbol-shuffling like this we’e safe from accidentally assuming something which isn’t justified. But we’re pretty far from understanding what these theorems even mean.

    In this case, these strings don’t mean anything. They’re a toy so we can get comfortable with the idea of building theorems this way. We don’t expect them to do any more work than we expect Lincoln Logs to build usable housing. But you can see how we’re starting pretty far from most interesting mathematics questions.

    Still, if we started from a system that meant something, we would get there in time, right? … Surely? …

    Well, maybe. The thing is, even with this I, M, U scheme and its four rules there are a lot of things to try out. From the first axiom, MI, we can produce either MII or MIM. From MII we can produce MIIM or MIIII. From MIIII we could produce MIIIIM, or MUI, or MIU, or MIIIIIIII. From each of those we can produce … quite a bit of stuff.

    All of those are theorems in this scheme and that’s nice. But it’s a lot. Suppose we have set up symbols and axioms and rules that have clear interpretations that relate to something we care about. If we set the computer to produce every possible legitimate result we are going to produce an enormous number of results that we don’t care about. They’re not wrong, they’re just off-point. And there’s a lot more true things that are off-point than there are true things on-point. We need something with judgement to pick out results that have anything to do with what we want to know. And trying out combinations to see if we can produce the pattern we want is hard. Really hard.

    And there’s worse. If we set up a formal language that matches real mathematics, then we need a lot of work to prove anything. Even simple statements can take forever. I seem to remember my logic professor needing 27 steps to work out the uncontroversial theorem “if x = y and y = z, then x = z”. (Granting he may have been taking the long way around for demonstration purposes.) We would have to look in theorems of unspeakably many symbols to find the good stuff.

    Now it’s reasonable to ask what the point of all this is. Why create a scheme that lets us find everything that can be proved, only to have all we’re interested in buried in garbage?

    There are some uses. To make us swear we’ve read Jorge Luis Borges, for one. Another is to study the theory of what we can prove. That is, what are we able to learn by logical deduction? And another is to design systems meant to let us solve particular kinds of problems. That approach makes the subject merge into computer science. Code for a computer is, in a sense, about how to change a string of data into another string of data. What are the legitimate data to start with? What are the rules by which to change the data? And these are the sorts of things grammars, and the study of grammars, are about.

     
    • Jacob Kanev 7:07 am on Tuesday, 15 March, 2016 Permalink | Reply

      A beautiful post, thank you; and very well explained. I remember our professor linking grammars and Turing machines with Church’s thesis, the fact that the brain is a deterministic machine, and Gödel’s theorem, to arrive at some pretty fundamental claims about perception and knowledge in general. Well, I guess every professor tries to sell their own subject as the most substantial of all. Although he was pretty successful with this one.

      Btw, I do have a wordpress blog: https://jacobkanev.wordpress.com/

      Like

      • Joseph Nebus 7:23 am on Wednesday, 16 March, 2016 Permalink | Reply

        I’m happy to be of service and glad that you liked the essay as it turned out.

        I’d agree with your professor in linking grammars to Turing machines and fundamental ideas about what knowledge we can have. Grammars are ways of describing what we can know about a system, and if we’re looking seriously into the subject that has to bring us to the decidability problems and the limits of knowledge. I’m less sure about perception, but I don’t know what case your professor made.

        And I’m glad for the blog link; thank you.

        Like

    • elkement (Elke Stangl) 7:45 am on Friday, 18 March, 2016 Permalink | Reply

      Great post! I was a die-hard Gödel-Escher-Bach fan :-) That book made my decision to difficult to choose between physics, math, or computer science.

      Like

  • Joseph Nebus 3:00 pm on Friday, 4 March, 2016 Permalink | Reply
    Tags: , , , , , , proof   

    A Leap Day 2016 Mathematics A To Z: Conjecture 


    For today’s entry in the Leap Day 2016 Mathematics A To Z I have an actual request from from Elke Stangl. I’d had another ‘c’ request, for ‘continued fractions’. I’ve decided to address that by putting ‘Fractions, continued’ on the roster. If you have other requests, for letters not already committed, please let me know. I’ve got some letters I can use yet.

    Conjecture.

    An old joke says a mathematician’s job is to turn coffee into theorems. I prefer tea, which may be why I’m not employed as a mathematician. A theorem is a logical argument that starts from something known to be true. Or we might start from something assumed to be true, if we think the setup interesting and plausible. And it uses laws of logical inference to draw a conclusion that’s also true and, hopefully, interesting. If it isn’t interesting, maybe it’s useful. If it isn’t either, maybe at least the argument is clever.

    How does a mathematician know what theorems to try proving? We could assemble any combination of premises as the setup to a possible theorem. And we could imagine all sorts of possible conclusions. Most of them will be syntactically gibberish, the equivalent of our friends the monkeys banging away on keyboards. Of those that aren’t, most will be untrue, or at least impossible to argue. Of the rest, potential theorems that could be argued, many will be too long or too unfocused to follow. Only a tiny few potential combinations of premises and conclusions could form theorems of any value. How does a mathematician get a good idea where to spend her time?

    She gets it from experience. In learning what theorems, what arguments, have been true in the past she develops a feeling for things that would plausibly be true. In playing with mathematical constructs she notices patterns that seem to be true. As she gains expertise she gets a sense for things that feel right. And she gets a feel for what would be a reasonable set of premises to bundle together. And what kinds of conclusions probably follow from an argument that people can follow.

    This potential theorem, this thing that feels like it should be true, a conjecture.

    Properly, we don’t know whether a conjecture is true or false. The most we can say is that we don’t have evidence that it’s false. New information might show that we’re wrong and we would have to give up the conjecture. Finding new examples that it’s true might reinforce our idea that it’s true, but that doesn’t prove it’s true.

    For example, we have the Goldbach Conjecture. According to it every even number greater than two can be written as the sum of exactly two prime numbers. The evidence for it is very good: every even number we’ve tied has worked out, up through at least 4,000,000,000,000,000,000. But it isn’t proven. It’s possible that it’s impossible from the standard rules of arithmetic.

    That’s a famous conjecture. It’s frustrated mathematicians for centuries. It’s easy to understand and nobody’s found a proof. Famous conjectures, the ones that get names, tend to do that. They looked nice and simple and had hidden depths.

    Most conjectures aren’t so storied. They instead appear as notes at the end of a section in a journal article or a book chapter. Or they’re put on slides meant to refresh the audience’s interest where it’s needed. They are needed at the fifteen-minute park of a presentation, just after four slides full of dense equations. They are also needed at the 35-minute mark, in the middle of a field of plots with too many symbols and not enough labels. And one’s needed just before the summary of the talk, so that the audience can try to remember what the presentation was about and why they thought they could understand it. If the deadline were not so tight, if the conference were a month or so later, perhaps the mathematician would find a proof for these conjectures.

    Perhaps. As above, some conjectures turn out to be hard. Fermat’s Last Theorem stood for four centuries as a conjecture. Its first proof turned out to be nothing like anything Fermat could have had in mind. Mathematics popularizers lost an easy hook when that was proven. We used to be able to start an essay on Fermat’s Last Theorem by huffing about how it was properly a conjecture but the wrong term stuck to it because English is a perverse language. Now we have to start by saying how it used to be a conjecture instead.

    But few are like that. Most conjectures are ideas that feel like they ought to be true. They appear because a curious mind will look for new ideas that resemble old ones, or will notice patterns that seem to resemble old patterns.

    And sometimes conjectures turn out to be false. Something can look like it ought to be true, or maybe would be true, and yet be false. Often we can prove something isn’t true by finding an example, just as you might expect. But that doesn’t mean it’s easy. Here’s a false conjecture, one that was put forth by Goldbach. All odd numbers are either prime, or can be written as the sum of a prime and twice a square number. (He considered 1 to be a prime number.) It’s not true, but it took over a century to show that. If you want to find a counterexample go ahead and have fun trying.

    Still, if a mathematician turns coffee into theorems, it is through the step of finding conjectures, promising little paths in the forest of what is not yet known.

     
    • elkement (Elke Stangl) 9:38 pm on Friday, 4 March, 2016 Permalink | Reply

      Thanks :-) So you say that experts’ intuition that might look like magic to laymen is actually pattern recognition, correct? (I think I have read about this in pop-sci psychology books) And if an unproven theorem passes the pattern recognition filter it is promoted to conjecture.

      Like

      • Joseph Nebus 7:27 am on Wednesday, 9 March, 2016 Permalink | Reply

        I think that there is a large aspect of it that’s pattern recognition, yes. But some of that may be that we look for things that resemble what’s already worked. So, like, if we already have a theorem about how a sequence of real-valued functions converges to a new real-valued function, then it’s natural to think about variants. Can we say something about sequences of complex-valued functions? If the original theorem demanded functions that were continuous and had infinitely many derivatives, can we loosen that to a function that’s continuous and has only finitely many derivatives? Can we lose the requirement that there be derivatives and still say something?

        I realized at one point while taking real analysis in grad school that many of the theorems we were moving into looked a lot like what we already had with one or two variations, and could sometimes write out the next theorem almost by rote. There is certainly a kind of pattern recognition at work here, though sometimes it can feel like playing with the variations on a theme.

        Liked by 1 person

        • elkement (Elke Stangl) 7:37 am on Wednesday, 9 March, 2016 Permalink | Reply

          Yes, I agree – I meant pattern recognition in exactly this way, in a very broad way … searching for a similar pattern in your own experiences, among things you have encountered and that worked. I was thinking in general terms and comparing to other skills and expertise, like what makes you successful in any kind of tech troubleshooting. It seems that you have an intuitive feeling about what may work but actually you draw on related scenarios or aspects of scenarios we had solved.

          Like

    • Pen & Shutter 1:09 pm on Saturday, 5 March, 2016 Permalink | Reply

      I understood all that! I definitely deserve a prize … I am no mathematician … And I enjoyed every word! I love your use of English.

      Like

    • davekingsbury 3:25 pm on Saturday, 5 March, 2016 Permalink | Reply

      If you’ve nothing for Q, what about Quadratic Equations … though I start twitching whenever I think about them!

      Like

      • Joseph Nebus 7:43 am on Wednesday, 9 March, 2016 Permalink | Reply

        I’m sorry to say Q already got claimed, by ‘quaternion’. But P got ‘polynomial’, which should be close enough to quadratic equations that there’s at least some help there.

        Liked by 1 person

  • Joseph Nebus 12:00 pm on Sunday, 25 October, 2015 Permalink | Reply
    Tags: , , , , proof,   

    Reading the Comics, October 22, 2015: Foundations Edition 


    I am, yes, saddened to hear that Apartment 3-G is apparently shuffling off to a farm upstate. There it will be visited by a horrifying kangaroo-deer-fox-demon. And an endless series of shots of two talking heads saying they should go outside, when they’re already outside. But there are still many comic strips running, on Gocomics.com and on Comics Kingdom. They’ll continue to get into mathematically themed subjects. And best of all I can use a Popeye strip to talk about the logical foundations of mathematics and what computers can do for them.

    Jef Mallett’s Frazz for the 18th of October carries on the strange vendetta against “showing your work”. If you do read through the blackboard-of-text you’ll get some fun little jokes. I like the explanation of how “obscure calculus symbols” could be used, “And a Venn diagram!” Physics majors might notice the graph on the center-right, to the right of the DNA strand. That could show many things, but the one most plausible to me is a plot of the velocity and the position of an object undergoing simple harmonic motion.

    Still, I do wonder what work Caulfield would show if the problem were to say what fraction were green apples, if there were 57 green and 912 red apples. There are levels where “well, duh” will not cut it. In case “well, duh” does cut it, then a mathematician might say the answer is “obvious”. But she may want to avoid the word “obvious”, which has a history of being dangerously flexible. She might then say “by inspection”. That means, basically, look at it and yeah, of course that’s right.

    Jeffrey Caulfield and Alexandre Rouillard’s Mustard and Boloney for the 18th of October uses mathematics as the quick way to establish “really smart”. It doesn’t take many symbols this time around, curiously. Superstar Equation E = mc2 appears in a misquoted form. At first that seems obvious, since if there were an equals sign in the denominator the whole expression would not parse. Then, though, you notice: if E and m and c mean what they usually do in the Superstar Equation, then, “E – mc2” is equal to zero. It shouldn’t be in the denominator anyway. So, the big guy has to be the egghead.

    Peter Maresca’s Origins of the Sunday Comics for the 18th of October reprints one of Windsor McCay’s Dreams of the Rarebit Fiend strips. As normal for Dreams and so much of McCay’s best work, it’s a dream-to-nightmare strip. And this one gives a wonderful abundance of numerals, and the odd letter, to play with. Mathematical? Maybe not. But it is so merrily playful it’d be a shame not to include.

    Zach Weinersmith’s Saturday Morning Breakfast Cereal for the 20th of October is a joke soundly in set theory. It also feels like it’s playing with a set-theory-paradox problem but I can’t pin down which one exactly. It feels most like the paradox of “find the smallest uninteresting counting number”. But being the smallest uninteresting counting number would be an interesting property to have. So any candidate number has to count as interesting. It also feels like it’s circling around the heap paradox. Take a heap of sand and remove one grain, and you still have a heap of sand. But if you keep doing that, at some point, you have just one piece of sand from the original pile, and that is no heap. When does the heap move away?

    Daniel Shelton’s Ben for the 21st of October is a teaching-arithmetic problem, using jellybeans. And fractions. Well, real objects can do wonders in connecting a mathematical abstraction to something one has an intuition for. One just has to avoid unwanted connotations and punching.

    Doug Savage’s Savage Chickens for the 21st of October uses “mathematics homework” as the emblem of the hardest kind of homework there might ever be. I saw the punch line coming a long while off, but still laughed.

    The Sea Hag is dismissive of scientists, who try to take credit for magic even though 'they can't even THINK! They have to use machines to tell them what two plus two is!! And another machine to prove the first one was right!'

    Bud Sagendorf’s Popeye for the 22nd of October, 2015. The strip originally ran sometime in 1981. This would be only a few years after the Four-Color Theorem was solved by computer. The computer did this by trying out all the possibilities and reporting everything was OK.

    Bud Sagendorf’s Popeye began what it billed as a new story, “Science Vs Sorcery”, on Monday the 19th. I believe it’s properly a continuation of the previous story, though, “Back-Room Pest!” which began the 13th of July. “Back-Room Pest!”, according to my records, originally ran from the 27th of July, 1981, through to the 23rd of January, 1982. So there’s obviously time missing. And this story, like “Back-Room Pest”, features nutty inventor Professor O G Wotasnozzle. I know, I know, you’re all deeply interested in working out correct story guides for this.

    Anyway, the Sea Hag in arguing against scientists claims “they can’t even think! They have to use machines to tell them what two plus two is!! And another machine to prove the first one was right!” It’s a funny line and remarkably pointed for an early-80s Popeye comic. The complaint that computers leave one unable to do even simple reasoning is an old one, of course. The complaint has been brought against every device or technique that promises to lighten a required mental effort. It seems to me similar to the way new kinds of weapons are accused of making war too monstrous and too unchivalrous, too easily done by cowards. I suppose it’s also the way a fable like the story of John Henry hold up human muscle against the indignity of mechanical work.

    The crack about needing another machine to prove the first was right is less usual, though. Sagendorf may have meant to be whimsically funny, but he hit on something true. One of the great projects of late 19th and early 20th century mathematics was the attempt to place its foundations on strict logic, independent of all human intuition. (Intuition can be a great guide, but it can lead one astray.) Out of this came a study of proofs as objects, as mathematical constructs which must themselves follow certain rules.

    And here we reach a spooky borderland between mathematics and sorcery. We can create a proof system that is, in a way, a language with a grammar. A string of symbols that satisfies all the grammatical rules is itself a proof, a valid argument following from the axioms of the system. (The axioms are some basic set of statements which we declare to be true by assumption.) And it does not matter how the symbols are assembled: by mathematician, by undergrad student worker, by monkey at a specialized typewriter, by a computer stringing things together. Once a grammatically valid string of symbols is done, that string of symbols is a theorem, with its proof written out. The proof is the string of symbols that is the theorem written out. If it were not for the modesty of what is claimed to be done — proofs about arithmetic or geometry or the like — one might think we had left behind mathematics and were now summoning demons by declaring their True Names. Or risk the stars overhead going out, one by one.

    So it is possible to create a machine that simply grinds out proofs. Or, since this is the 21st century, a computer that does that. If the computer is given no guidance it may spit out all sorts of theorems that are true but boring. But we can set up a system by which the computer, by itself, works out whether a given theorem does follow from the axioms of mathematics. More, this has been done. It’s a bit of a pain, because any proofs that are complicated enough to really need checking involve an incredible number of steps. But for a challenging enough proof it is worth doing, and automated proof checking is one of the tools mathematicians can now draw on.

    Of course, then we have the problem of knowing that the computer is carrying out its automatic-proof programming correctly. I’m not stepping into that kind of trouble.

    The attempt to divorce mathematics from all human intuition was a fruitful one. The most awe-inspiring discovery to come from it is surely that of incompleteness. Any mathematical system interesting enough will contain within it statements that are true, but can’t be proven true from the axioms.

    Georgia Dunn’s Breaking Cat News for the 22nd of October features a Venn Diagram. It’s part of how cats attempt to understand toddlers. My understanding is that their work is correct.

     
  • Joseph Nebus 2:00 pm on Sunday, 11 October, 2015 Permalink | Reply
    Tags: , , proof   

    The Kind Of Book That Makes Me Want To Refocus On Logic 


    For my birthday my love gave me John Stillwell’s Roads to Infinity: The Mathematics of Truth and Proof. It was a wonderful read. More, it’s the sort of read that gets me excited about a subject.

    The subject in this case is mathematical logic, and specifically the sections of it which describe infinitely large sets, and the provability of theorems. That these are entwined subjects may seem superficially odd. Stillwell explains well how the insights developed in talking about infinitely large sets develops the tools to study whether logical systems are complete and decidable.

    At least it explains it well to me. I know I’m not a typical reader. I’m not certain if I would have understood the book as well as I did if I hadn’t had a senior-level course in mathematical logic. And that was a long time ago, but it was also the only mathematics course which described approaches to killing the Hydra. Stillwell’s book talks about it too and I admit I appreciate the refresher. (Yeah, this is not a literal magical all-but-immortal multi-headed beast mathematicians deal with. It’s also not the little sea creature. What mathematicians mean by a ‘hydra’ is a branching graph which looks kind of like a grape vine, and by ‘slaying’ it we mean removing branches according to particular rules that make it not obvious that we’ll ever get to finish.)

    I appreciate also — maybe as much as I liked the logic — the historical context. The development of how mathematicians understand infinity and decidability is the sort of human tale that people don’t realize even exists. One of my favorite sections mentioned a sequence in which great minds, Gödel among them, took turns not understanding the reasoning behind some new important and now-generally-accepted breakthroughs.

    So I’m left feeling I want to recommend the book, although I’m not sure who to. It’s obviously a book that scouts out mathematical logic in ways that make sense if you aren’t a logician. But it uses — as it must — the notation and conventions and common concepts of mathematical logic. My love, a philosopher by trade, would probably have no trouble understanding any particular argument, and would probably pick up symbols as they’re introduced. But there’d have to be a lot of double-checking notes about definitions. And the easy familiarity with non-commutative multiplication is a mathematics-major thing, and to a lesser extent a physics-major thing. Someone without that background would fairly worry something weird was going on other than the weirdness that was going on.

    Anyway, the book spoke to a particular kind of mathematics I’d loved and never had the chance to do much with. If this is a field you feel some love for, and have some training in, then it may be right for you.

     
    • Barb Knowles 12:32 pm on Monday, 12 October, 2015 Permalink | Reply

      I am not a mathematician by any stretch of the imagination. But I love words and ideas and the birth and history of those words and ideas. Thank you for this interesting post.

      Like

  • Joseph Nebus 8:19 pm on Thursday, 23 October, 2014 Permalink | Reply
    Tags: , , , , proof   

    Calculus without limits 5: log and exp 


    I’ve been on a bit of a logarithms kick lately, and I should say I’m not the only one. HowardAt58 has had a good number of articles about it, too, and I wanted to point some out to you. In this particular reblogging he brings a bit of calculus to show why the logarithm of the product of two numbere has to be the sum of the logarithms of the two separate numbers, in a way that’s more rigorous (if you’re comfortable with freshman calculus) than just writing down a couple examples along the lines of how 102 times 103 is equal to 105. (I won’t argue that having a couple specific examples might be better at communicating the point, but there’s a difference between believing something is so and being able to prove that it’s true.)

    Like

    Saving school math

    The derivative of the log function can be investigated informally, as log(x) is seen as the inverse of the exponential function, written here as exp(x). The exponential function appears naturally from numbers raised to varying powers, but formal definitions of the exponential function are difficult to achieve. For example, what exactly is the meaning of exp(pi) or exp(root(2)).
    So we look at the log function:-
    calculus5 text
    calculus5 pic

    View original post

     
    • howardat58 8:41 pm on Thursday, 23 October, 2014 Permalink | Reply

      Hey thanks, Joseph.
      I quite agree with your comment about examples. Yes, examples first, then you know why you are trying to prove something generally.

      Like

      • Joseph Nebus 4:13 am on Wednesday, 29 October, 2014 Permalink | Reply

        Thank you. I’ve wondered sometimes if the whole trick to teaching mathematics is figuring out just enough examples to set up the generalization, and then a couple examples to show why the generalization works. It’s surely got to be more than that, though.

        Like

  • Joseph Nebus 11:42 pm on Monday, 28 October, 2013 Permalink | Reply
    Tags: , , , proof   

    The Big Zero 


    I want to try re-proving the little point from last time, that the chance of picking one specific number from the range of zero to one is actually zero. This might not seem like a big point but it can be done using a mechanism that turns out to be about three-quarters of all the proofs in real analysis, which is probably the most spirit-crushing of courses you take as a mathematics undergraduate, and I like that it can be shown in a way that you can understand without knowing anything more sophisticated than the idea of “less than or equal to”.

    So here’s my proposition: that the probability of selecting the number 1/2 from the range of numbers running from zero to one, is zero. This is assuming that you’re equally likely to pick any number. The technique I mean to use, and it’s an almost ubiquitous one, is to show that the probability has to be no smaller than zero, and no greater than zero, and therefore it has to be exactly zero. Very many proofs are done like this, showing that the thing you want can’t be smaller than some number, and can’t be greater than that same number, and we thus prove that it has to be that number.

    Showing that the probability of picking exactly 1/2 can’t be smaller than zero is easy: the probability of anything is a number greater than or equal to zero, and less than or equal to one. (A few bright people have tried working out ways to treat probabilities that can be negative numbers, or that can be greater than one, but nobody’s come up with a problem that these approaches solve in a compelling way, and it’s really hard to figure out what a negative probability would mean in the observable world, so we leave the whole idea for someone after us to work out.) That was easy enough.

    (More …)

     
  • Joseph Nebus 3:49 pm on Friday, 31 May, 2013 Permalink | Reply
    Tags: Goldbach's Conjecture, , , , proof, twin primes   

    Odd Proofs 


    May 2013 turned out to be an interesting month for number theory, in that there’ve been big breakthroughs on two long-standing conjectures. Number theory is great fun in part because it’s got many conjectures that anybody can understand but which are really hard to prove. The one that’s gotten the most attention, at least from the web sites that I read which dip into popular mathematics, has been the one about twin primes.

    It’s long been suspected that there are infinitely many pairs of “twin primes”, such as 5 and 7, or 11 and 13, or 29 and 31, separated by only two. It’s not proven that there are such, not yet. Yitang Zhang of Harvard has announced proof that there are infinitely many pairings of primes that are no more than 70,000,000 apart. This is admittedly not the tightest bound out there, but it’s better than what there was before. But while there are infinitely many primes — anyone can prove that — how many there are in any fixed-width range tends to decrease, and it would be imaginable to think that the distance between primes just keeps increasing, without bounds, the way that (say) each pair of successive powers of two is farther apart than the previous pair were. But it’s not so, and that’s neat to see.

    Less publicized is a proof of Goldbach’s Odd Conjecture. Goldbach’s Conjecture is the famous one that every even number bigger than two can be written as the sum of two primes. An equivalent form would be to say that every whole number — even or odd — larger than five can be written as the sum of three primes. Goldbach’s Odd Conjecture cuts the problem by just saying that every odd whole number greater than five can be written as the sum of three primes. And it’s this which Harald Andres Helfgott claims to have a proof for. (He also claims to have a proof that every odd number greater than seven can be written as the sum of three odd primes, that is, that two isn’t needed for more than single-digit odd numbers.)

    (More …)

     
    • elkement 12:58 pm on Saturday, 1 June, 2013 Permalink | Reply

      I have a stupid question: Why is this that you can prove the conjecture for all numbers higher than a certain threshold? Why does the proof work for number > 10 to the power of 30, but not for smaller onces? What is special about 10_30?

      Like

      • Joseph Nebus 5:27 pm on Saturday, 1 June, 2013 Permalink | Reply

        It’s not a stupid question although it’s one I’m not sure I can answer quite well enough given that a lot of the paper calls on things that I don’t know well.

        If I am reading it correctly, the core idea of the proof is to substitute summations over numbers (as, you might, sum over primes) with integrals. This is an approximation, yes, but if you’re summing over a large enough number of small enough things, that substitution becomes as accurate as you could possibly need. Again, if I have this correctly, then, the bound of 10^{30} comes about because for numbers smaller than that bound, the integral approximation isn’t quite close enough to the summation to guarantee that there aren’t any overlooked numbers.

        I’d defer happily to the expertise of anyone who does know number theory better and can more confidently follow the course of the proof. I admit I’m intimidated just by some of the symbols (a valentine heart as a subscript? How did that come about?) and, after all, it is a 130-page proof.

        Like

        • elkement 4:42 pm on Sunday, 2 June, 2013 Permalink | Reply

          Thanks a lot! Replacing sums by integral is very common in solid state physics (summing over all electron states…), so I can relate to that. I would not have expected that in pure mathematcs though!

          Like

          • Joseph Nebus 4:56 pm on Sunday, 2 June, 2013 Permalink | Reply

            Quite glad to help (assuming I have got it right).

            I should say for anyone who’s reading this but never ventured far enough into calculus to look at integrals on purpose, the point of replacing summations with integrals is that, generally, it’s a lot easier to study integrals than it is summations. So if you can replace a summation with an integral you’re probably well-off doing that, although often, you can only make that replacement if it’s a sum over many enough pieces.

            Like

    • Danny Sichel 2:10 pm on Saturday, 16 July, 2016 Permalink | Reply

      “And yet you know just what I mean, too, and trying to be clear about what I mean would produce a pile of unintelligible words”

      hm. How about saying ‘its full decmial expansion is nearly seven million digits’ ?

      Like

      • Joseph Nebus 4:28 pm on Wednesday, 20 July, 2016 Permalink | Reply

        Yeah, you’re right. That works. Sometimes I don’t know how to say things clearly. Thank you.

        Like

  • Joseph Nebus 10:57 pm on Friday, 26 April, 2013 Permalink | Reply
    Tags: , , , , obituaries, , proof   

    Kenneth Appel and Colored Maps 


    Word’s come through mathematics circles about the death of Kenneth Ira Appel, who along with Wolgang Haken did one of those things every mathematically-inclined person really wishes to do: solve one of the long-running unsolved problems of mathematics. Even better, he solved one of those accessible problems. There are a lot of great unsolved problems that take a couple paragraphs just to set up for the lay audience (who then will wonder what use the problem is, as if that were the measure of interesting); Appel and Haken’s was the Four Color Theorem, which people can understand once they’ve used crayons and coloring books (even if they wonder whether it’s useful for anyone besides Hammond).

    It was, by everything I’ve read, a controversial proof at the time, although by the time I was an undergraduate the controversy had faded the way controversial stuff doesn’t seem that exciting decades on. The proximate controversy was that much of the proof was worked out by computer, which is the sort of thing that naturally alarms people whose jobs are to hand-carve proofs using coffee and scraps of lumber. The worry about that seems to have faded as more people get to use computers and find they’re not putting the proof-carvers out of work to any great extent, and as proof-checking software gets up to the task of doing what we would hope.

    Still, the proof, right as it probably is, probably offers philosophers of mathematics a great example for figuring out just what is meant by a “proof”. The word implies that a proof is an argument which convinces a person of some proposition. But the Four Color Theorem proof is … well, according to Appel and Haken, 50 pages of text and diagrams, with 85 pages containing an additional 2,500 diagrams, and 400 microfiche pages with additional diagrams of verifications of claims made in the main text. I’ll never read all that, much less understand all that; it’s probably fair to say very few people ever will.

    So I couldn’t, honestly, say it was proved to me. But that’s hardly the standard for saying whether something is proved. If it were, then every calculus class would produce the discovery that just about none of calculus has been proved, and that this whole “infinite series” thing sounds like it’s all doubletalk made up on the spot. And yet, we could imagine — at least, I could imagine — a day when none of the people who wrote the proof, or verified it for publication, or have verified it since then, are still alive. At that point, would the theorem still be proved?

    (Well, yes: the original proof has been improved a bit, although it’s still a monstrously large one. And Neil Robertson, Daniel P Sanders, Paul Seymour, and Robin Thomas published a proof, similar in spirit but rather smaller, and have been distributing the tools needed to check their work; I can’t imagine there being nobody alive who hasn’t done, or at least has the ability to do, the checking work.)

    I’m treading into the philosophy of mathematics, and I realize my naivete about questions like what constitutes a proof are painful to anyone who really studies the field. I apologize for inflicting that pain.

     
    • elkement 11:46 am on Saturday, 27 April, 2013 Permalink | Reply

      I had once enjoyed Simon Singh’s book on Andrew Wiles’ life-task of developing a proof for Fermat’s Last Theorem … and I also wondered how many people actually really have followed each step.

      Like

      • Joseph Nebus 4:52 pm on Wednesday, 1 May, 2013 Permalink | Reply

        I realize on thinking about it I’m not sure whether I’ve read Singh’s book on Andrew Wiles or not. I know I’ve read at least one of his books, but my records on this stuff are all a mess.

        Great mathematics puzzles are often split between those which have great stories behind them and those which are just, “this nagged at mathematicians for a long while, until someone had a breakthrough”. I wonder if the difference is actually whether the problem was something that could be explained to a lay audience briefly, or whether at least one Great Weird Mathematics Personality got involved, or whether there just are some things that have histories that can’t be made interesting no matter how important they are. (Keep in mind, I’m a person who owns multiple pop histories of containerized cargo and am glad to.)

        Like

    • elkement 8:27 pm on Tuesday, 30 April, 2013 Permalink | Reply

      Joseph, I enjoy following your blog(s), so I have nominated you for the Liebster blog award. These are the “rules”, but feel free to respond in any way you prefer – I did not really follow the rules last time ;-)
      http://elkement.wordpress.com/2013/04/30/liebster-blog-award-this-time-i-try-to-respond-in-a-more-normal-way/

      Like

      • Joseph Nebus 4:49 pm on Wednesday, 1 May, 2013 Permalink | Reply

        Well, goodness, thank you. I intend to give a reply in kind, and appreciate your thinking of me.

        Like

  • Joseph Nebus 6:46 pm on Saturday, 22 December, 2012 Permalink | Reply
    Tags: , , existence proof, , proof,   

    Keep The Change 


    I’m sorry to have fallen quiet for so long; the week has been a busy one and I haven’t been able to write as much as I want. I did want to point everyone to Geoffrey Brent’s elegant solution of my puzzle about loose change, and whether one could have different types of coin without changing the total number of value of those coins. It’s a wonderful proof and one I can’t see a way to improve on, including an argument for the smallest number of coins that allow this ambiguity. I want to give it some attention.

    The proof that there is some ambiguous change amount is a neat sort known as an existence proof, which you likely made it through mathematics class without seeing. In an existence proof one doesn’t particularly care whether one finds a solution to the problem, but instead bothers trying to show whether a solution exists. In mathematics classes for people who aren’t becoming majors, the existence of a solution is nearly guaranteed, except when a problem is poorly proofread (I recall accidentally forcing an introduction-to-multivariable-calculus class to step into elliptic integrals, one of the most viciously difficult fields you can step into without requiring grad school backgrounds), or when the instructor wants to see whether people are just plugging numbers into formulas without understanding them. (I mean the formulas, although the numbers can be a bit iffy too.) (Spoiler alert: they have no idea what the formulas are for, but using them seems to make the instructor happy.)

    (More …)

     
    • Geoffrey Brent (@GeoffreyBrent) 11:07 pm on Saturday, 22 December, 2012 Permalink | Reply

      Well, I managed to improve on it by fixing another error of mine ;-) Fortunately not a fatal one!

      I’m glad you liked it. It’s been so long since I’ve done an existence proof (back in uni, one of my calculus lecturers gave me a funny look when I went the other way and gave a constructive proof to an existence question).

      Like

      • Chiaroscuro 6:36 am on Sunday, 23 December, 2012 Permalink | Reply

        I also quite appreciated it; I figured you’d take my setup and to good things with it. (As a horribly lapsed math-fan, I’m resigned to such occasional nudges.) :)

        Like

  • Joseph Nebus 2:30 am on Friday, 23 March, 2012 Permalink | Reply
    Tags: , , , proof,   

    Proving A Number Is Not 1 


    I want to do some more tricky examples of using this ε idea, where I show two numbers have to be the same because the difference between them is smaller than every positive number. Before I do, I want to put out a problem where we can show two numbers are not the same, since I think that makes it easier to see why the proof works where it does. It’s easy to get hypnotized by the form of an argument, and to not notice that the result doesn’t actually hold, particularly if all you see are repetitions of proofs where things work out and don’t see cases of the proof being invalid.

    (More …)

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
%d bloggers like this: