Mathematics - 2012-01-12 (page 2 of 3)

Kannappan Sampath

15:11

@Asaf Hello

@Dylan Hello, Welcome!

Asaf Karagila

What's up?

Daniil

Oh man, thanks god for youtube.

Kannappan Sampath

@Asaf Can you explain to me the construction of group structure over an arbitrary set using Axiom of Choice?

Daniil

I watched waaay too much comedy shows today, thanks to holidays.

Kannappan Sampath

Oh sorry, the connection lost me!!

robjohn

15:26

@Skullpatrol Um, yes, and where do you think I contradicted that?

Skullpatrol

@robjohn No ... that was my mistake ... I misunderstood you

robjohn

Okay. Derivation of the solution usually goes something like "if $f(x)=0$ then $x=1$" whereas the check would go something like "if $x=1$ then $f(x)=0$"

Asaf Karagila

@KannappanSampath For example, $M$ is an infinite set, then $\bigoplus_M\mathbb Z$ has the same cardinality as $M$.

Kannappan Sampath

ok.

Skullpatrol

@robjohn I got confused when you said " Without reversible operations, we have not said that if x=3 then 3x+2=11,"

Asaf Karagila

15:31

Now take $f:M\to\bigoplus_M\mathbb Z$ which is bijective and use it to define the group action.

Daniil

What is $\bigoplus_M\mathbb Z$?

Asaf Karagila

:2974554 It is the direct sum of copies of $\mathbb Z$ over the index set which is $M$.

Kannappan Sampath

you beat me to it, @AsafKaragila

Daniil

Ah

Asaf Karagila

You can think of it as the functions from $M$ into $\mathbb Z$ that only finitely many elements are sent to a non-zero integer.

Kannappan Sampath

15:33

wait i still didn't get!

Daniil

And why is it a group? What is the group operation here?

Skullpatrol

@robjohn Yes that is my point: "if f(x)=0 then x=1" whereas the check would go something like "if x=1 then f(x)=0" one is the converse of the other, right?

Asaf Karagila

@Daniil Pointwise addition.

Daniil

Hm, I might not understand the concept of the direct sum then. What is $0_0 + 0_1 =$?

where 0 and 1 are elements from M

Kannappan Sampath

@AsafKaragila If I understand right, you say that $f$ takes an element from $M$ to a sequence in Z which has only finitely many non-zero entries, am I right?

Asaf Karagila

15:37

@Daniil: $f_1:M\to\mathbb Z$ and $f_2:M\to\mathbb Z$ has a natural addition defined on them:

$$f_1+f_2(m) = f_1(m)+f_2(m)$$

If you require that each function has only finitely many points for which $f(m)\neq 0$ then the cardinality of this group is the same as $M$.

Kannappan Sampath

@AsafKaragila Was I right in somesense?

Skullpatrol

@robjohn So the truth of the converse condition provides us with a check for errors that may occur in solving equations, right Rob?

Asaf Karagila

@KannappanSampath Yeah.

@Daniil The elements are not directly from $M$ but rather functions from $M$ into $\mathbb Z$. The addition is defined at the range, rather than in the domain.

However, since the cardinality of $M$ and $\bigoplus_M\mathbb Z$ is the same, we can define a bijection between the two sets and use it to define the addition on $M$.

Daniil

ah, I see

We can do that with any group, can we? Not just Z

any infinite*

Asaf Karagila

Yeah. It's just very convenient with $\mathbb Z$.

Kannappan Sampath

15:41

If M is finite, what do we do? we just need to prove that there exists group of order $n$ for every natural number $n$. Right?

@AsafKaragila

Asaf Karagila

@KannappanSampath Then take $\mathbb Z/n\mathbb Z$.

Daniil

@KannappanSampath take an underlying group of a ring

yeah

robjohn

@Skullpatrol well, what we are trying to find is an $x$ for which $f(x)=0$, so the converse checks that we have indeed found it.

Kannappan Sampath

@AsafKaragila I get your point.

Is this the same as Hogtarts Construction I had seen once on MO

Asaf Karagila

Hogtarts?

Kannappan Sampath

15:44

Maybe I am mispelling it?

robjohn

@AsafKaragila Sounds like some motorcycle porn or something.

Hogtart of the month

Kannappan Sampath

what?

Asaf Karagila

I don't watch Motorcycle porn :-D

Srivatsan

@robjohn Googling for "Hogtarts" gives me "Hogwarts" as the first result.

robjohn

@Srivatsan I'm not surprised.

Srivatsan

15:47

Yes, they sound different, but their spellings are incredibly close to each other.

Asaf Karagila

@KannappanSampath Hartog?

Kannappan Sampath

Yeah.

Just looked up MO\

Daniil

lol

Asaf Karagila

Hartog's number is not related to that. It is how you prove that this is equivalent to the axiom of choice.

Skullpatrol

@robjohn So when asked "why are we plugging it back in?" and "why does it work?" the answer is "We are checking the truth of the converse"

Srivatsan

15:48

@AsafKaragila In fact, it's "Hartogs" (I think)

Kannappan Sampath

Yes it is!

Srivatsan

@Skullpatrol No. We are plugging it in to make sure we did not get an extraneous solution.

robjohn

@Srivatsan That is probably because it redirected the search to "Hogwarts" if you tell it that you really meant "Hogtarts" you get a search for that. for example

Kannappan Sampath

And @AsafKaragila I'd like to learn that as well

mathoverflow.net/questions/12973/…

Srivatsan

@robjohn May be. I was just amused to find Hogwarts.

Asaf Karagila

15:50

@KannappanSampath Do you know anything about ordinals?

robjohn

@Skullpatrol No, we are checking the truth of the original statement. We have used the converse to get the solution.

@Srivatsan That's what I figured that Kannappan actually meant.

Kannappan Sampath

Yes. But very lttle, that I can distinguish between 1+\omega and \omega +1 are different

Note that I can distinguish!!

And, I can define it as well!

Asaf Karagila

For a set $X$ the Hartogs number of $X$ is the least ordinal $\alpha$ that there is no injective $f:\alpha\to X$.

Srivatsan

@robjohn Are you joking or serious?

Asaf Karagila

Hang on, I wrote an explanation about it on JDH's cardinals wiki.

Kannappan Sampath

15:53

@Srivatsan So, can we discuss the answer!

to the problem about Uniform continuity!!

robjohn

@Srivatsan I was serious. I wasn't paying attention to the context, so when I saw "Hogtarts", I thought, "did he misspell Hogwarts?"

Asaf Karagila

@Kannappan Hartogs number. It's not long but it should do, I hope.

Srivatsan

@KannappanSampath Not really. Not just now.

Kannappan Sampath

@Srivatsan Fine with me!

robjohn

10 mins ago, by Asaf Karagila

Hogtarts?

Srivatsan

15:55

@KannappanSampath Sorry, I keep catching you at all the wrong times. (And it's not even a big deal. I just didn't understand the intuition...)

robjohn

@Srivatsan That's what I saw at first.

Kannappan Sampath

@AsafKaragila I think I am not lost. So, we can move further!

Srivatsan

@robjohn OK. If Asaf said it, he probably misspelled Hogwarts - maybe even intentionally. =)

Asaf Karagila

Where to?

Kannappan Sampath

to the proof of equivalence!

Asaf Karagila

15:57

Between the two things? Well, we've seen how AC implies how every set can be a group.

Kannappan Sampath

Yeah!

Asaf Karagila

In the other direction, the MO post is quite simple.

Kannappan Sampath

@Srivatsan I didn't understand!

Asaf Karagila

We simply use this to show that $X$ can be injected into its Hartogs, and thus can be well ordered.

Srivatsan

@KannappanSampath I just meant I am supposed to be doing some thing else right now. In fact, I'll have to go soon.

Kannappan Sampath

16:00

@Srivatsan OK fine I say! We can discuss sometime later!!

@AsafKaragila Going through MO post.

Srivatsan

@KannappanSampath Hey, it seems you are angry...

Kannappan Sampath

Thanks for taking time for me!!

@Srivatsan No, why would I be angry? No Problem at all!

Srivatsan

With your double exclamations, it just seemed so. =) Try reading this from my point of view: "OK fine I say! We can discuss sometime later!!"

Kannappan Sampath

@Srivatsan Yeah I am feeling the same too...

Srivatsan

I mean: it's fine even if you're. It just won't get you anything, so why bother being angry? =) // Anyway, that was just what went through my mind; we can maybe stop this talk here.

Kannappan Sampath

16:07

@Srivatsan Just started writing out blogs man!

It's a lot of fun you know!

Do you write one?

Srivatsan

No. Send us a link.

Are you guys not discussing something more important? About Hartogs number?

Kannappan Sampath

@Srivatsan We just finished, I was pointed to the MO post, I'll find sometime to read it.

Skullpatrol

@robjohn So is the structure: If original equation, then transform into simpler final equation. Check: If final equation, then plug into original equation to check for truth.

QED

hello

Kannappan Sampath

@Srivatsan I only have one post. The point I brought this up is to know the other blogs I can point to. (Other than Tao and Gowers).

Skullpatrol

16:11

@QED Hey agent Q

Kannappan Sampath

@QED Hello, welcome board!

QED

thanks

Srivatsan

@KannappanSampath Ah, that makes sense. I guess Tao and Gowers will be in everyone's lists. =) But I don't have a blog.

I think you should convince Asaf to start one so that you can point to his.

Kannappan Sampath

@Srivatsan I remember reading in the transript, where Asaf politely refused to write one!

Skullpatrol

Q (James Bond)

Q is a fictional character in the James Bond novels and films. Q (standing for Quartermaster), like M, is a job title rather than a name. He is the head of Q Branch (or later Q Division), the fictional research and development division of the British Secret Service. The character actually appears only fleetingly in Ian Fleming's novels, but comes into his own in the successful Bond film series; he is also mentioned in the continuation novels of John Gardner and Raymond Benson. Q has appeared in 19 of 22 Eon Bond films; all except Live and Let Die, Casino Royale and Quantum of Solace. Th...

Asaf Karagila

16:13

I said that yesterday. I often have the idea of writing a blog, but I know that very fast I'll stop adding stuff to it. So what's the point?

Kannappan Sampath

@AsafKaragila But, I am pretty sure, you can't feel like it! That's the point when you have readership!

Almost every math.SE r would follow yours!!!

Asaf Karagila

I had a photography blog a couple of year back. It had plenty of followers and whatnot. I just stopped updating one day, and then I closed it up completely.

Srivatsan

How long did you maintain it?

Asaf Karagila

I think about a year or so.

Kannappan Sampath

I am eagerly writing a post for publishing this weekend.

I plan to keep all my notes on the blog; no hifi stuff though!

But it's a kind of good.

Srivatsan

16:21

Extra publicity for jury work. [Or is this extra publicity not needed?]

Kannappan Sampath

@Srivatsan I think it can be closed as EXACT Duplicate, but I am of no help though.

Skullpatrol

@robjohn Am I on the right track with the structure sir? If original equation, then transform into simpler final equation. Check: If final equation, then plug into original equation to check for truth.

Srivatsan

@KannappanSampath Yes, that's what he have voted it to be.

Kannappan Sampath

OK, I think I'll leave now.

QED

bye

Skullpatrol

16:36

@QED Bye agent Q

Daniil

"Since decision problems and languages are different characterizations of the same concept". Can somebody please explain that to me?

QED

I'm not sure I totally agtree with that

Daniil

Does that mean that checking whether a string is in a language is a decision problem?

QED

but let P(n) be some predicate on natural numbers

Daniil

(I am trying to grasp a concept of defining complexity classes via languages)

QED

16:45

then the decision problem "P or not P" is equivalent to deciding whether a string "n" is in the language {n in N|P(n)}

Daniil

Ah, I see.

Thanks.

Asaf Karagila

@Mike!! Long time no see!

Mike Spivey

@AsafKaragila Hi, Asaf. :) Yes, it's been a while; I've been busier than usual lately. I did drop by yesterday to chat with Srivatsan for a while.

I see that in my absence I am no longer a worthy rival for you in the rep race. :)

Asaf Karagila

Yeah. I had a lucky strike of several days with capping out.

I also began writing my thesis and consider a blog.

Mike Spivey

@AsafKaragila Good for you! This is your master's, right?

Asaf Karagila

16:55

Indeed.

The working title is on the starred list, bold font.

Mike Spivey

The "Russell's Strange Socks Drawer..." nice. :) At first I missed the "bold font" part and thought that you were referring to one of the pinned comments. For a couple of seconds I thought that meant your working title was "The horror... The horror..." :)

Asaf Karagila

Hah :-D

So how have you been doing?

Mike Spivey

There were many times during my thesis I felt like it was "The horror... The horror..." :)

Daniil

What is a "proof string" in terms of computation?

QED

@Sasha discuss.area51.stackexchange.com/questions/3766/…

@Daniil, where did you read that?

badp

16:59

@Sasha please keep in mind that promotion needs to go with disclosure - if you want to promote Mathematica.SE, feel free to do so, but you must also disclose you work for Mathematica

QED

@hobodave, can you stop these spam people

we are getting this almost daily

hobodave

is it actually spam?

QED

yes

Mike Spivey

@AsafKaragila Pretty well. I've been working on some of my own problems more lately. I finally found an answer to that combinatorial proof question I asked a few months back that got so many upvotes. That was satisfying.

QED

in the past we've had people who are just going through every single SE room posting their link

hobodave

17:00

oh, sorry I wasn't fully informed

hi @badp

Asaf Karagila

@MikeSpivey Nice!

badp

(Which is totally rad, by the way. Grats for landing a job on such a company. Wolfram Alpha is a boon to humanity.)

Mike Spivey

@AsafKaragila The holidays are always busy, too, and we had family visiting for a while.

Asaf Karagila

@MikeSpivey I see. Holidays suck :-)

Daniil

@QED qwiki.stanford.edu/index.php/Petting_Zoo

badp

17:01

(welcome back @Sasha)

Daniil

"Perhaps unsurprisingly, restricting by space instead of time allows for a lot more power. For instance, it is trivial to see that PSPACE contains every problem in NP: simply iterate through all possible proof strings "

Sasha

@badp Thanks. I did not mean to spam.

badp

@Sasha I know, hence the unsuspension

just a reminder of the promotion rules here on SE :)

QED

@Daniil, are you familiar with tyhe idea of a "proof object"?

Daniil

@QED no

Mike Spivey

17:03

@AsafKaragila Next week I start consulting for an investments firm for several months. That will be different and hopefully fun. It will also mean much less time on math.SE.

QED

@Daniil, a simple example is that a bijection f : X -> Y proves that X and Y are equinumerous

Asaf Karagila

@MikeSpivey Aww :(

QED

@Daniil, so you can view a bijection as a proof that |X| = |Y|

Daniil

Sorry?

Mike Spivey

@Asaf: What else is new with you? Although I suppose starting your thesis is enough big news. :)

Daniil

17:04

@QED I completely agree with you :) But I do not understand what does it have to do with proof strings?

QED

@Daniil, this is an example of a proof object

Asaf Karagila

@MikeSpivey Not too much, really. I am working and working and working, but not really working :-D

QED

@Daniil, another example is - if you claim to have solved some puzzle you can prove that by giving the list of moves you need to do to solve it

Daniil

Ah, I see.

QED

@Daniil, so in that case a string of moves is the proof object

Asaf Karagila

17:06

I am tempted to comment/edit iyengar's "master Gauss" and "the great mathematician Glaois" words.

Daniil

So, speaking in terms of languages, what would that be?

QED

@Daniil, anyway, the idea here with P vs NP is that there are algorithms which seem to take a massive amount of computation to do -- but once you've done it, it's easy to check if you've got a correct answer

@Daniil, so your proof string in this case is something like a "string of moves" or an assignment of variables to values or something - which is polynomial time checkable

Daniil

@QED Ok, can you explain to me this part about PSPACE then: "Perhaps unsurprisingly, restricting by space instead of time allows for a lot more power. For instance, it is trivial to see that PSPACE contains every problem in NP: simply iterate through all possible proof strings (which have to be polynomially short) and check each one in turn. "

This implies that there is some unified notion of proof string which has to be polynomially short, doesn't it?

QED

@Daniil, it's necessarily going to take up no more than polynomial space, if you can possibly check it in polynomial time

Asaf Karagila

@Mike So you're taking a break from the uni?

Daniil

17:10

@QED I see. And how are you going to get those proofs?

QED

what do you mean?

Mike Spivey

@AsafKaragila I'm on sabbatical this year. I got tenure last year (yay!), so this year I'm on the standard post-tenure sabbatical. I spent the fall working on some of my own research projects (and hanging out on math.SE more than usual :) ), and this spring I've lined up this consulting gig with an investments firm.

Asaf Karagila

Nice!!!

QED

They just gave an algorithm for solving NP problems in PSPACE. Exercise: Find an algorithm for solving NP problems in PTIME.

Asaf Karagila

Post-tenure sabbatical sounds awesome "You worked hard, you won the race. Take a year to rest."

Daniil

17:13

Well, we can solve any NP problem in polynomial space by iterating over all possible proof strings, but were are those proof strings coming from? Are they runs of the machine which solves a problem in NP?

QED

@Daniil, being in NP means you have a fast (= polynomial time) method of checking whether or not a proof proves something: For example if I give you my list of moves you can check if it solves the puzzle by trying them out.

@Daniil, so the proof that NP is contained in PSPACE works by enumerating all strings without even thinking about it (this takes exponential time) and checking whether or not each one is a correct proof or not

So you're running a PTIME algorithm EXP many times. PSPACE means it doesn't take up much space but it can take as much time as you want

Daniil

But what if there are infinite amount of strings? The machine won't halt

QED

@Daniil, so the strings could be like "up", "down", "up up", "up down", "down down", ...

yes there are infinitely many

Mike Spivey

@AsafKaragila It is nice to have several months to focus just on research - and then to try something totally new for another few months.

QED

in that example

@Daniil, but we should pick a concrete NP-complete problem and look at what the proof strings are like

Asaf Karagila

17:16

@MikeSpivey Sounds like fun, indeed.

QED

@Daniil, lookj here en.wikipedia.org/wiki/Boolean_satisfiability_problem - this one is to find a boolean variable assignment: so there are only 2^n strings

Daniil

Yes, it's clear for SAT problem.

Mike Spivey

@AsafKaragila You'll get there yourself someday, Asaf. :) Are you hoping to land a job in Israel when you finish your PhD? Or go somewhere else?

Asaf Karagila

I told my students yesterday that if one of them solves the SAT problem they should give me acknowledgment for whatever :-P

QED

is there a particular one which is confusing?

Daniil

17:18

But what if we have such problem: given a binary string, check whether the first character is 1. This is a NP problem, right?

Asaf Karagila

@MikeSpivey I don't really mind going somewhere else, my girlfriend got a USA citizenship. I guess if we get married by then I'll have a green card or something.

Daniil

It can be solved on non-deterministic Turing machine in polynomial time.

QED

@Daniil, the input (all possible binary strings) is a different concept to the proof string: What does a proof that 10101100 starts with 1 look like?

Daniil

@QED I don't know :(

QED

@Daniil, the proof strings for this problem you mentioned are trivial: You don't even need any every proof can be the empty strings so there is exactly 1 of them

Daniil

17:21

Ah, okay.

QED

@Daniil, what I mean by that is: you don't need any special information to check in PTIME that 101011 starts with 1

Daniil

Thank you, QED.

I understand it now.

QED

great

Daniil

I also have another question, if you have time. How can one show that if a problem can be solved in polynomial time on non-deterministic Turing machine then the proof can be checked in polynomial time on regular Turing machine.

QED

you just give an execution trace for what the non-deterministic TM went through

then the normal TM can follow it

Daniil

17:25

Ah, true.

Thank you.,

Mike Spivey

@robjohn: My apologies for bringing up an ancient chat message, but Paul's answer and my answer on this question aren't really the same. Paul fixes n and does induction on k. I hold the difference between n and k fixed and give a recurrence that involves increasing both of them simultaneously.

@robjohn: (continued) The integration by parts formula turns out to be a little different - and a little cleaner, I think, which is why I posted the answer.

robjohn

@MikeSpivey Did I say differently? I thought all the answers were nice, but I pointed out in a comment to the OP that induction works for integers, but if you want more generality, more involved methods are available.

@MikeSpivey I'm sorry if I slighted your answer, but I didn't intend to.

Mike Spivey

17:43

@robjohn Here's the comment I was referring to. I don't consider your comment a slight at all. I just thought you misunderstood what I was doing, and so I wanted to point that out. No offense taken!

And "Hi", by the way. :)

robjohn

@MikeSpivey It's been a while, but I think that my comment was based on the fact that the arguments were based on showing a recursion proved using integration by parts. The recursions shown are different, but my comment was pretty vague about what "pretty close" meant.

Mike Spivey

@robjohn In that sense, yes, the answers are pretty close.

robjohn

@MikeSpivey I think I was still thinking that there are two sorts of proofs, discrete using integration by parts, and continuous using the Beta function. It happens when I'm in a certain frame of mind. :-) I have trouble remembering that three comes next :-)

QED

what sort of efficient algorithms are there to compute far out terms of linear recurrences?

I guess we can do things a bit like binary exponentiation sometimes [always?]

Mike Spivey

@robjohn What's new with you?

robjohn

17:55

@QED Can you solve it in closed form?

QED

they all have closed forms in terms of algebraic exponentials

robjohn

@MikeSpivey Work is getting busy with the new year. I have been away from getting high rep days over the holidays, and now work is getting in the way :-)

@MikeSpivey How about with you?

QED

I think I can always do something like binary exponentiation, but it takes log(n) matrix inversions

robjohn

@QED matrix inversions?

QED

if a_n is a recurrence so is a_{2n}, but I have to invert a matrix to find it

Mike Spivey

17:59

@robjohn I've been busier lately, too - family visiting, holiday activity, working on some of my own problems rather than trying to solve other people's on math.SE. :)

robjohn

@QED So you don't know the solution in closed form?

QED

I can write it in terms of exponentials of algebraic numbers

robjohn

@MikeSpivey Ah, productive problems. That sounds good.

QED

This is the sort of matrix inversion I mean math.stackexchange.com/questions/94359/…

Mike Spivey

@robjohn I also started writing a book last month - on different methods for proving binomial coefficient identities. We'll see if it ever gets finished, but in the meantime it's been fun working on it.

robjohn

18:05

@MikeSpivey That I would be interested in! I have a few tricks, but I'm sure there are many more.

@QED what are you inverting there?

@QED never mind. I see.

Mike Spivey

@robjohn I've learned a lot from thinking about others' questions and answers on this site. If the book ever gets finished there will be one big "thank you" to MSE in the acknowledgements.

robjohn

@MikeSpivey Did you see this answer? I used some binomial identities in the proof of $(5)$, but the key fact, that $\operatorname{Re}\left(\frac{1}{e^{ix}+1}\right)=\frac12$ eluded me for a while. It disturbs me since I spent quite a while with inversion.

Mike Spivey

@robjohn No, I didn't. Thanks for pointing it out. I'll take a closer look at it later.

robjohn

@MikeSpivey I have some questions I need to as about David Speyer's answer keying on the idea that he seems to solve $\left( 1+a_1 x + a_2 x^2 + \cdots + a_m x^m \right) \sqrt{1-x} = \left( 1+b_1 x + b_2 x^2 + \cdots + b_m x^m \right) + O(x^{n+1})$ for $a_n$ and $b_n$. I think that one can find a $\{b_n\}$ for any $\{a_n\}$.

QED

18:43

you can compute something like a_{7*5+3} really quickly by shifting the series 3 then diving it by 7 then computing the 5th term

actually dividing requires more than a matrix inversion, you need to compute a few terms ahead 7*degree I guess

with some work you could probably make this sort of approach efficient, I wonder if there are different ways to speed up though

robjohn

@QED Is that easier than computing $a_{38}$ using the closed form?

QED

I don't know

robjohn

@QED Do you know that $F_{n+2k}=(2F_{k+1}-F_{k})F_{n+k}-(-1)^kF_n$

This gives a recursion for any size step.

yoda

boy, someone got flagged & banned for posting a link to an Area 51 proposal? harsh.

robjohn

e.g. $F_{n+10}=11F_{n+5}+F_n$

QED

18:59

@robjohn, I think we always have relations of this form [for any recurrence]. The most efficient (and only) way I know of computing them is via matrix inverse

robjohn

@QED How do you do the 5-step recurrence with matrices? The one I show above.

QED

@robjohn, just compute a_5, a_10, ... then fit an order n recurrence to it

robjohn

@QED Ouch!

QED

you don't like that?
:)

is there some better way

robjohn

Do you think that is how I got $F_{n+2k}=(2F_{k+1}-F_{k})F_{n+k}-(-1)^kF_n$?

QED

19:02

that's F for fibonacci numbers?

robjohn

Yeah

QED

then I think you're doing something special that only works for fibonacci numbers

robjohn

I plugged in $k=5$ for the formula above

@QED absolutely not.

Suppose the $S$ is the shift operator: $Sa_{n}=a_{n+1}$

Then for the Fibonacci sequence we have that $(S^2-S-1)F_n=0$

Any polynomial multiple of $S^2-S-1$ will kill $F_n$

So we just need to find a polynomial multiple of $S^2-S-1$ that only involves powers of $S^k$

Suppose we have the factorization $(S-a)(S-b)=S^2-S-1$

Asaf Karagila

Cranky...

QED

can you find that mechanically, by just reducing the polynomials you get from commutators?

robjohn

19:09

What does $(S^k-a^k)(S^k-b^k)$ look like?

anon

@Asaf: "If there was a mistake, it would have been founded already."

robjohn

$S^{2k}-(a^k+b^k)S^k+(ab)^k$

@QED "the polynomials you get from commutators"?

QED

as in Bills answer

robjohn

@QED Do you see how, using Bill's method to immediately get the $k=5$ case that I give above? Perhaps I don't understand everything about Bill's method.

that is, without computing all intermediate cases.

QED

I thought you were using that stuff, since you mentioned S

I don't know how to turn what Bill wrote into an algorithm

robjohn

19:18

Okay, back to what I was saying...

anon

Just started reading a proof of Kummer's lemma, and I have 2 questions: (a) I see that $(1-\zeta)^p\cong_{p}0$ hence $p\in\mathbb{Z}[\zeta]$ isn't prime, but how do we get that $(p)=(1-\zeta)^{p-1}$?; (b) how is $u\equiv\overline{u}$ obtained at the top of pg2?

robjohn

So we get that anything that satisfies $(S-a)(S-b)a_n=0$ will satisfy $(S^k-a^k)(S^k-b^k)a_n=0$ since $S^k-a^k$ is a polynomial multiple of $S-a$. Got that?

@QED $S$ is just a common operatorname for "shift operator"

QED

I don't really understand it

how do you know that S-b|(S^k-a^k)(S^k-b^k)?

oh that's fine

it's a commutative ring

anon

(Sorry for the interruption. Also that should be $(1-\zeta)^p\equiv_p0$.)

robjohn

Since $S-b|S^k-b^k$

so are you okay so far?

QED

19:22

yes

robjohn

@anon not to worry :-)

anon

Surely the shift operator commutes with scalar multiplication.

robjohn

So we have that $S^{2k}-(a^k+b^k)S^k+(ab)^k$ kills $a_n$. Does that go through?

QED

cool

robjohn

and $a^k+b^k$ is just a combination of Fibonacci numbers in the Fibonacci case.

$2F_{k+1}-F_{k}$ to be exact :-)

QED

19:25

I can see how that works in general, and how it's much faster. All we need to do is compute some symmetric power sums

robjohn

@QED Yes.

Asaf Karagila

@anon Well, it's too late for an edit now.

anon

Ah, anyone remember this question?

Asaf Karagila

I cut my finger while washing the dishes. Argh.

QED

19:54

any mention of godel is automatic upvotes

robjohn

@QED I added what I said here as an answer. I hope that doesn't step on any toes.

QED

funnily enough I'm reading it already!

Asaf Karagila

@robjohn I'll start saying "Godel" in every post :D

Matt

Would anyone like to help me resolve my confusion that I have expressed in the comment to the answer here?

Asaf Karagila

@Matt: The closed sets can be internally defined as the collection of limit points within the space.

$[0,1]\cap\mathbb Q$ is closed in $\mathbb Q$ but not in $\mathbb R$.

Matt

20:05

But it doesn't contain all of its limit points whether you consider it a subset of $\mathbb{Q}$ or of $\mathbb{R}$!

Asaf Karagila

WHEN

Matt

What?

Asaf Karagila

Read this

robjohn

@AsafKaragila Gödel that sounds Gödel like a Gödel good idea Gödel

Asaf Karagila

@robjohn One cannot upvote chat messages!

robjohn

20:07

@AsafKaragila I was seeing whether it works for stars :-)

Matt

@AsafKaragila Seriously? $\sqrt{2}$ is not a limit point of $\mathbb{Q}$ "in" $\mathbb{Q}$?

Asaf Karagila

Yes.

Much like if $M[G]$ is a generic extension of $M$ adding a new subset of $\omega$, then $M$ does not know this subset.

Matt

I'll have to delete my comment to Jonas' answer.

anon

A limit point of X in Y has to actually exist in Y I believe.

Asaf Karagila

@anon You believe right.

Matt

20:09

I refuse to believe.

robjohn

@Matt is $\sqrt{2}\in\mathbb{Q}$?

Matt

@robjohn No.

Asaf Karagila

@Matt Who are you? Fox Mulder?

Matt

@AsafKaragila No then I'd have written "I want to believe."

@anon Thank you.

Asaf Karagila

But you don't want to believe the government :-P

robjohn

20:11

@Matt The truth is out there

Matt

I really liked X Files. Although the writing went downhill after the first two seasons.

Asaf Karagila

Not sure that two seasons, but after six - for sure.

Matt

: D

@AsafKaragila I still refuse to believe. $\sqrt{2}$ is a limit point of $\mathbb{Q}$ whichever way you look at it.

Blimey, you nearly managed to confuse me there.

Asaf Karagila

20:31

Then what is $\mathbb R$ if not the metric completion of $\mathbb Q$?

QED

can you state the definition @Matt

Matt

@AsafKaragila Exactly. I wasn't saying anything else.

QED

then we can actually figure out if it's true or not

Asaf Karagila

Wha?

anon

By the way, Who is on first base.

robjohn

20:32

BBL

Matt

I'm going to pop out now. Have a good one.

Asaf Karagila

@anon I'm on first base, and second and third. I am everywhere!

Transcript for

$Mathematics$ Mathematics