X^2 is the sum of three periodic functions | Hacker News Reader

X^2 is the sum of three periodic functions

gotmath.com

206 pointsColinWright53 comments

I hesitate to say this, but ...

If you think this belongs on the front page of HN then you need to up-vote it. Any moment now it will trigger the flame-war detector, get a penalty in the ranking score, and disappear without trace. Anything with 40 comments and fewer points than comments gets such a penalty, and while it's a good proxy for flame-war detection, is does get quite a lot of false positives.

If you want this to avoid that fate, you need to up-vote it. If you don't really care, then that's fine. I think it's interesting, but not everyone does.

Added in edit - something has giving this item a penalty[0] - maybe there are people who've flagged it as inappropriate. Certainly it doesn't seem to have tripped the "flame-war" detector, but who can tell.

[0] http://hnrankings.info/7056295/

> Anything with 40 comments and fewer points than comments gets such a penalty, and while it's a good proxy for flame-war detection

Is this really true? There's a strong implication there that the typical HN account is more likely to upvote an article than to comment on one. I upvote comments all the time, and comment frequently, but I almost never upvote articles (though I did find this one to be a great mix of interestingness with accessibility).

See the section "Controversy" in this article:

http://www.righto.com/2013/11/how-hacker-news-ranking-really...

Discussed at length here:

https://news.ycombinator.com/item?id=6799854

One side-effect is that it's starting to stifle genuine discussion, as people decline to comment/reply for fear of an interesting item getting penalized off the front page.

I'm guilty of almost never upvoting articles—it's because I'm too lazy. Also the voting buttons are tiny. I actually do appreciate the reminder.

Sadly some of us don't have enough karma for our upvotes to be counted, it appears. Hmmm.

While I'm at it let me plug a slightly similar concept to the posted article, in terms of decomposing things and representation via series: Fibonacci coding. Not sure how obscure it is but only learnt of it recently: http://en.wikipedia.org/wiki/Fibonacci_coding

> It is clear that a non-constant polynomial cannot be expressed as a finite sum of continuous periodic functions,

But it can be expressed as an infinite sum of continuous periodic functions, right? I seem to remember that you could use all the sine functions as bases for the vector space of functions and (almost?) any function could be expressed as an infinite sum of sines.

It's been a while since I've thought about these things, is that recollection correct?

Yup! This is the basis for Fourier analysis: http://en.wikipedia.org/wiki/Fourier_analysis

Except that the author is referring to the entire domain (where a polynomial cannot be represented as a countably infinite sum of periodic functions), while a Fourier transform of a function has to be taken over a finite region like [a,b].

I'm pretty sure a Fourier _transform_ is over the entire domain while a Fourier _series_ is over a periodic function or finite region.

Yes, but only on a finite open interval, that is (a, b) with a, b real numbers.

In the post the sum of periodic functions is equal to x^2 on the whole real line. This is impossible with sums of continuous periodic functions, such as Fourier series, because continuous periodic functions are bounded, while x^2 is unbounded.

> This is impossible with sums of continuous periodic functions, such as Fourier series, because continuous periodic functions are bounded, while x^2 is unbounded.

But infinite sums of continuous periodic functions are not necessarily bounded: sin(x) + sin(x/2) + sin(x/4) + ... is an example. So there has to be something else to the proof.

You are right, but I was referring to either finite sums or Fourier series, your example is not one because sum of the squares of the coefficients is infinite. I don't know what can be said about arbitrary countable/uncountable sums of continuous periodic functions.

I think the thing which is defeating my intuition here is the continuity issue.

"If a periodic function is continuous and nonconstant, then it has a least period, and all other periods are positive integer multiples of the least period."

I think my naive intuition is modelling "periodic function" as "continuous and periodic". Basically, I'm not exercising the the full freedom of the "it's periodic" concept.

There's a good Feynman anecdote on this (from Surely You're Joking...):

------

"I had a scheme, which I still use today when somebody is explaining something that I'm trying to understand: I keep making up examples.

For instance, the mathematicians would come in with a terrific theorem, and they're all excited. As they're telling me the conditions of the theorem, I construct something which fits all the conditions. You know, you have a set (one ball)-- disjoint (two balls). Then the balls turn colors, grow hairs, or whatever, in my head as they put more conditions on.

Finally they state the theorem, which is some dumb thing about the ball which isn't true for my hairy green ball thing, so I say "False!" [and] point out my counterexample."

------

So I think it's useful to consider the most extreme thing which meets your criteria, instead of a "representative" example.

To come back to tech I think a similar mindset is also useful for things like system failure mode analysis. "Yes, but what if that switch dies at the same time...?"

They point out early in the text that the Dirichlet function is periodic (indeed, periodic with every rational number as a period).

Considering that might help?

The Axiom of Choice defeats all intuition.

It's very interesting but why isn't there any practical example? What are the equations of three periodic functions that would add up to y = x^2 for instance?

How would one even construct those three equations? If I'm not mistaken TFA demonstrates that these functions exist, not how to find them.

I wish I hadn't stopped with maths in high school...

Brief answer: the author invokes the Axiom of Choice, so the three equations will be really screwball and there will be no way to write them down explicitly.

This is, in some sense, regarded as cheating. (The Axiom of Choice is generally accepted as a legitimate mathematical axiom, but not universally.)

http://en.wikipedia.org/wiki/Axiom_of_choice

You are right, the demonstration is only partially constructive. The functions are well defined: they are the canonical projectors of the Hamel basis. The trick is, the basis itself is not constructible.

There are no practical examples. The solutions are unbounded, discontinuous functions (that wont have nice equations) and since the proof uses the axiom of choice it is fundamentally non constructive (meaning you would need a totally different proof technique to be able to build a concrete solution)

I can't quite follow your thinking here?

> If I'm not mistaken TFA demonstrates that these functions exist, not how to find them.

Completely correct.

> why isn't there any practical example?

You answer this yourself... the article demonstrates that the functions exist. It can't demonstrate the functions themselves; no one can do that.

It was when the article introduced "Lebesgue measurable periodic functions" without any explanation whatsoever that I realized that I was not going to understand this article at all (at least not without spending a day on Wikipedia).

Can someone who understands this please make a graph? Pics or it didn't happen.

Disclosure: the full article is a joke.

Why do you say that?

Disclosure - the article is not a joke, but exploits the fact that when you think you have a definition that captures some intuitive concept, sometimes it allows things you didn't expect.

Sadly, there is no known method of constructing such a Hamel basis — but we know there is one contained in the Cantor set [1].

[1] http://en.wikipedia.org/wiki/Cantor_set

Heads up: In section "A polynomial of degree n is the sum of n+1 periodic functions" it says 'cdots' in two formulas. (Probably a backslash missing in the TeX(?) source.)

Fun fact about considering R as a vector space over Q: the Hamel basis A mentioned in the post is not only infinite, but even uncountable.

I can see now why some mathematicians would like to do without axiom of choice.

Consider the product of two sets, A and B:

  A x B = { (a,b): a in A, b in B }

Pretty obviously if A and B are both non-empty, the product is non-empty.

The axiom of choice says that this is still true even when you take the product of infinitely many sets. Without the axiom of choice, the product of infinitely many non-empty sets could be empty.

Is that a better choice?

Infinty is unreal. Any formal intuition we build around it is free to choose. If you can imagine base of R then surely you can imagine infinite number of nonempty sets that have empty cartesian product. They might all be not empty but be sort of asymptotically empty, like probably not empty but with that probabiliy going to zero as number of sets goes to infinity.

The question is, does any good physics come from the axiom of choice?

  > If you can imagine base of R then surely you can
  > imagine infinite number of nonempty sets that have
  > empty cartesian product.

So you think it's OK to have infinitely may sets and not be able to choose one from each of them, even though they're all non-empty? That's a choice you're free to make, of course, but to me it seems more perverse than the alternatives.

  > The question is, does any good physics come from
  > the axiom of choice?

Does it matter? Once you're dealing with uncountable infinities you're already outside physics and pursuing things because they're interesting, not because they have immediate practical implications. Of course, bits of pure math has a tendency to crop up and be useful decades later, and you never know which bits that will be.

Weird things happen when you go from "every" to "all" for uncountable infinities. Loosing ability to pick elements wouldn't be the weirdest.

Physics matters. But since math is purely intelectual thing of course you are welcomed to pursue both paths. After all physics is not the only game we play. If someting is not useful in the real world it can be useful in virtual worlds we construct. All math is eventually applied math is a self fullfilling prophecy.

Most mathematitians choose to accept axiom of choice because it makes lots of things easier and lots even possible. It isn't better in any other sense than the oposite.

How do you feel about well ordering the reals? Because the Axiom of Choice gives you that too and so much more. I'm not a zealot one way or another, but don't argue for it based on intuition, it plays both ways.

As the old joke goes: We all know that the Axiom of Choice is true, Well-Ordering of the Reals is false, and who knows about Zorn's Lemma.

I use AC when I need it, avoid it when I can do without it, and sometimes look at what it allows versus what it implies.

I've never really understood why the well-ordering theorem is the version of the axiom of choice that's supposed to be "obviously false". It's pretty trivial to see how you get it from the AC, and since the AC is "obviously true" I've always felt the well-ordering theorem is intuitive as well. (Actually, my mental model of the process generally leads me to want to think "all sets are countable"... c'est la vie :/ )

The Banach-Tarski theorem, on the other hand, is much more robustly "obviously false".

"So you think it's OK to have infinitely may sets and not be able to choose one from each of them, even though they're all non-empty?"

There's a lot hidden behind the word "choose". Of course I have no objection to you just grabbing whatever out of each set, but when you "choose" by performing an arbitrarily unbounded computation, it sounds less un-perverse. I am aware I've implicitly used a constructivist formulation by reference any sort of "computation".

Personally I'm ambivalent about the axiom itself, I just think it should always be clear whether or not you've chose it, which is generally itself not a problem, so, generally I'm happy either way. It is the case that when you use the Axiom of Choice, you've just irretrievably left the physical universe, which is fine, but worth being aware of.

> The question is, does any good physics come from the axiom of choice?

In the first place, this isn't the question.

In the second place, obviously, no good physics comes from the axiom of choice, just as no good physics comes from denying the axiom of choice. If there were any known practical applications, they would be mentioned as soon as you heard of the thing.

Infinity is unreal...

Well, it allows quite a few arguments concerning asymptotics of algorithms, for example.

The "reality" of a concept is something on which many litres of ink and blood have been shee.

Yes. We reason about infinities. But when it comes to result we are always interested in with what's well before it.

> Without the axiom of choice, the product of infinitely many non-empty sets could be empty.

This sounds like a stupid question, but I can't really figure it out: How could it be empty, given your above formula?

(Math level: Engineer)

Edit: Wait, is it because every set contains the empty set? And without choosing you could end up with the empty set?

This is what the axiom of choice is about. It says:

    Given a collection of non-empty sets, there exists
    a "choice function" that chooses one element from
    each set.  (AC)

The problem is, AC can be used to prove all sorts of counter-intuitive results. The example that turns up here on HN all the time is Banach-Tarski[0][1], but this submission about x^2 being the sum of three periodic functions is another.

AC has been proven to be independent of the usual axioms of set theory, so in some sense you can choose whether to believe it or not. If it's true then Banach-Tarski is true. If it's false then you can have infinitely many non-empty sets with an empty Cartesian product. (corrected to read "an empty" instead of the error "a non-empty" - thanks thaumasiotes)

Pure math be crazy. And cool.

[0] http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox

[1] https://www.hnsearch.com/search#request/all&q=banach+tarski

----

Edit: No, it's not because of your edit:

    > ... is it because every set contains the empty set?
    > And without choosing you could end up with the empty set?

Not every set contains the empty set as an element, but every set has the empty set as a subset. We are talking about choosing elements, and the it that says "non-empty set" means that for every individual set we can choose one of its elements. The problem comes in that when there are infinitely many, including possibly uncountably infinitely many, we need to do all these choices "at once" (in some sense).

> If it's false then you can have infinitely many non-empty sets with a non-empty Cartesian product.

with an empty Cartesian product, I think?

Thanks! Yes, I have seen Banach-Tarski before, here and elsewhere. My confusion was mostly due to not thoroughly remembering what an axiom is... I expected there to be some kind of proof, like an example of a series of non-empty sets that have an empty set as their product.

    Pure math be crazy. And cool.

Indeed pretty cool. Thanks for submitting this fascinating link.

    Not every set contains the empty set as an element, but every set has the empty set as a subset.

Yes, I mixed this up quite badly.

First things first:

> Wait, is it because every set contains the empty set?

No. For example, the set {1} contains only one element, the integer 1, and does not contain the empty set.

> This sounds like a stupid question, but I can't really figure it out: How could it be empty, given your above formula?

The axiom of choice is called an axiom for a reason. It states that the cartesian product of infinitely many non-empty sets contains at least one element. So under the assumption that the axiom of choice is true, obviously, the product of non-empty sets cannot be empty, because that's the definition of the axiom of choice.

Conversely, under the assumption that the axiom of choice is false, there must be some infinite collection of non-empty sets for which the cartesian product is empty. Many people (like you!) find this absurd; thinking it's absurd doesn't indicate any problems with your intuition.

Now, there's a saying about the axiom of choice:

    The axiom of choice is obviously true,
    the well-ordering principle is obviously false,
    and who can tell about Zorn's lemma?

It's a joke; the three items mentioned are all known to be equivalent.

The axiom of choice is known to have equally "absurd" consequences. One, referenced in the above joke, is that it is equivalent to the statement

    All sets have a well-ordering

Which can be rephrased:

    For any set S, all subsets of S contain a least element

You might want to reflect on what the least element of the open interval (0,1) would be. (Note, "least" refers to the well-ordering of the set guaranteed to exist by the axiom of choice; it does not refer to the numeric sense in which 3 is less than 4.)

The axiom of choice also gives us the Banach-Tarski theorem, which says that a sphere can be divided into a finite number of pieces which can then be rearranged without deformation into two spheres of the same radius.

I generally lump anti-choice mathematicians into the same group as constructivists, but theoretically there could be a distinction. There are no known consequences (outside of the various theorems proved using the axiom, all rather abstruse) to believing one way or the other, but it's a rather emotional subject for many people. Why, I couldn't tell you.

    The axiom of choice is called an axiom for a reason.

    [...] thinking it's absurd doesn't indicate any problems with your intuition.

Thanks, that is exactly what I needed to read :)

    You might want to reflect on what the least element of the open interval (0,1) would be.

Am I right in assuming that I can not find any such element with my "intuition", but the axiom guarantees that there is a least element?

> Am I right in assuming that I can not find any such element with my "intuition", but the axiom guarantees that there is a least element?

Well... the second half of that is true. As to the first half, it's not so much that you can't find such an element... you could arbitrarily designate any number in the interval as the "least element", and that would be fine.

Going into it a little more:

Talking about ordering a set, we can define an ordering relation, traditionally called something like <= , to compare two elements. It can be pretty much anything at all; for example, over the set {1,2,3,8} I could define the relation like so, with five parts: 1 <= 1; 2 <= 2; 3 <= 3; 8 <= 8; 2 <= 8. That reflects the idea that they're all equal to themselves, and 2 is less than 8. Any other pair, like 2 and 3, is incomparable under the relation I've defined. In that set, under that relation, the subset {3} has a least element, 3; the subset {2,8} has a least element, 2; and the subset {1,3} doesn't have a least element because 1 and 3 are incomparable.

For a set to be well-ordered, you need some additional properties:

- the order relation must be total, that is, every two elements must be comparable to each other.

- every subset must have a least element under the relation

Using the standard numeric comparison <= , the positive integers are well ordered: any subset, even an infinite one has a least element (though not necessarily a greatest element). The integers are not well ordered under numeric comparison, as they have no least element (-4 is less than -3, but -5 is even less, and so on). But I can easily define a well order "W" on the integers by saying: a W b iff |a| < |b| or (|a| = |b| and a <= b). That W relation produces the order 0 W -1 W 1 W -2 W 2 W -3 ....... , and I can use it to define a least element of any subset of integers.

But you don't have to have an elegant-looking rule to define a well-order. As long as you can choose a least element from any subset, you're good. So if you say "the least element, in my well ordering, of the interval (0,1) is the square root of 1/2", there isn't any problem with that.

However, a constructivist will ask you "what is the least element of the set consisting of all real numbers between 0 and 1, except the square root of 1/2?". And it can be hard to justify the numbers you pick. So I guess human intuition usually doesn't extend to the idea that you can just keep picking seemingly-arbitrary least elements indefinitely (and since the reals are uncountable, you'd actually have to do that an uncountable number of times).

The axiom of choice solves the problem pretty directly; one of its standard formulations is

    For any collection of nonempty sets, there is a "choice function" f
    which maps every set in the collection to one of its own elements

And so to well-order the reals, you just say the collection of sets will be the set of subsets of the reals, and the least element of any given subset is the value of the choice function f for that subset.

EDIT:

The part in italics above is incorrect (I don't know how to produce strikethrough, or if it can even be done). This always messes me up. In my head, you just repeat the process I described above an impossibly large number of times: least element to be f(R), second least element to be f(R without the least element), etc. But as I mentioned elsewhere, that intuition always leads me into "all sets are countable", which I know is wrong. :(

Anyway, given a subset of R, you can't just apply the choice function; you'd have to start from R and keep applying the choice function and removing values until you got one which was in your subset.

As a (beginner) constructionist, the problem is not that the product "could be empty", but just that the product can't be constructed.

I view this in a similar way to Russell's Paradox (while I'm not claiming the axiom of choice leads to a contradiction) -- we can define how we can construct new objects, and we can say you can't invoke the axiom of choice, but have to give an explicit choice function.

This easily follows from the fact that R itself is uncountable. Otherwise it's trivial to enumerate all real numbers based on their decomposition.

"By repeating this, we find that e^x is the sum of 1 periodic function. But this is absurd."

No, it's not absurd.

e^x is periodic with period 2 Pi I.

Maybe the article was limiting itself to real functions and the existence thereof, but this example raised eyebrows.

The first sentence: "A real function is said to be periodic if there exists a real number P > 0 so that f(x+P) = f(x) for all x." Complex numbers aren't mentioned at all.

Another fun (and seemingly nonsensical) thing you can prove if you use the Axiom of Choice:

http://en.wikipedia.org/wiki/Banach-Tarski_paradox

What is a neat characteristics of N^2 where N is integer is that its value is the sum of the first N odd integers.

1^2 = 1 2^2 = 1 + 3 = 4 3^2 = 1 + 3 + 5 = 9 4^2 = 1 + 3 + 5 + 7 = 16 ...

I am wondering if there is a relation of this to the article.

Not really. First of all, the article is about real-valued functions while your fact is only interesting for integers. Secondly, the article is about polynomials in general, meaning that the proof still works if you multiply everything by a constant factor and add terms of a lower degree. The reason this matters is that sum(i^k for i from 1 to N) will always be a polynomial of degree (k+1) and the only special thing about your sum in this case (not having a constant factor or lower order tems) is not something tha the proof in the article cares about.

Reply on news.ycombinator.com