Mathematics - 2015-01-25 (page 2 of 4)

user91500

11:01

@JankoBracic I think you must wait at least 2 days.

evinda

11:47

@DanielFischer Hello!!!
Suppose that we have the following AVL-tree and want to delete 19:

@DanielFischer Will the result be the following?

Or am I wrong?

Janko Bracic

@user91500 Thank you! I guess that you are right, that one needs to wait 2 days.

Chris's sis

12:20

I'm away for some hours, I visit some relatives.

(not too much time for math these days - unfortunately)

evinda

Then I deleted 4 and I got this:

and then I deleted 56 and got this:

Could you tell me if it is right? Because in my lecture notes, there are different results... :/

Daniel Fischer

13:20

@evinda That's one possibility. One could also implement deletion of a node with two children such that the largest node in the left subtree replaces the deleted, then it would look different (after replacing, you'd then need rotations to make it an AVL tree again). Your trees after the further deletions look fine to me. How do the results in your lecture notes look?

evinda

13:31

@DanielFischer So does this mean that the result depend on which node we choose to replace with the one that we want to delete? These are the results in my lecture notes:

@DanielFischer I think that they deleted first other nodes.. I will try it again...

Daniel Fischer

@evinda In particular the last looks like they use a completely different deletion algorithm. Of course, if one uses different algorithms, different results are to be expected.

evinda

13:52

@DanielFischer I retried it... At each step except from the last one, I get the same result..
After having deleted 4, we have this tree:

Then after deleting 56, I get this tree:

and the result of my lecture notes is this one:

@DanielFischer Is my result also right?

Daniel Fischer

@evinda Different algorithm for deletion. Look at how deletion is described in your lecture notes.

Both results are AVL trees, so both are correct in that sense.

evinda

@DanielFischer Initially, we follow the known algorithm of deletion in a binary tree:
1)deletion of the node v itself, if it is a leaf.
2)replacement with its child if it has only one.
3)replacement with its next in the in-order traversal if it has two children.
Balance
- If 1) or 2) the balance of the parent node w of v changes.
- If 3) the balance of the parent node w of the next of v in the in-order traversal changes.

Daniel Fischer

@evinda Okay, so we're in case 3, and the next node in the in-order traversal is 90. For some reason, in the lecture notes, a left rotation was done, although that isn't necessary to have an AVL tree. Don't ask me why.

evinda

@DanielFischer A ok.. So my result is correct, right? :)

Daniel Fischer

14:10

@evinda Correct in the sense that you get a valid AVL tree. If a specific deletion strategy is prescribed, it may be incorrect in that sense.

evinda

@DanielFischer At the beginning of the algorithm, it says that "we check the whole path from w till the root and for each node of this path that has balance +2 or -2 after the deletion, maybe rotations will be needed as follows... "
But in our case the node with key 56 is the root.. :/

Daniel Fischer

That makes for a short path. So you'd check whether the root node has, after deletion, a balance of $\pm 2$, find that it doesn't, and hence should not rotate.

evinda

So we just have to replace 56 with 90, right? @DanielFischer

Daniel Fischer

And remove the old 90 node.

A Beautiful Mind

@DanielFischer May I ask why you did not become a mathematician?

evinda

14:22

Yes :) Thanks a lot!!!

Daniel Fischer

@ABeautifulMind I don't think there's a law against asking. Can't give much of an answer, though, it just didn't work out that way.

A Beautiful Mind

@DanielFischer I see. My life also did not work out as planned. I am still struggling with mental illness, and this will be my 9th year of not working.

Chris's sis

14:42

@ABeautifulMind see here

►

@ABeautifulMind humiliate your every single negative thought by a positive one.

user153330

@Chris'ssis hi! so you're now a motivational speaker? : P

Chris's sis

Never accept to be down!

@user153330 hello (well, once in a while ;))

user153330

@Chris'ssis btw i think this mate is the best motivational speaker on math.SE

Syuizen

:) How to type LateX quickly? When I edit my answer on Mathstackexchange, it usually takes 20 min .

Chris's sis

@user153330 Well, I see things approximately the same.

user153330

15:01

hella @N3buchadnezzar

how're ya?

^^^ @BalarkaSen

^^^ @TedShifrin you want kill me right?

Ramanewbie

@user153330 he doesn't seem to be there...

user153330

15:19

@Ramanewbie are you sure?

Ramanewbie

@user153330 I can't see his avatar on the list on the right of the page.

user153330

@Ramanewbie when he logs in he'll see the message : )

Ramanewbie

@user153330 I bet so... ^^

user153330

@Ramanewbie as you say baby hippa

Ramanewbie

@user153330 "baby hippa" lol, eveyone calls me like this -_-

N3buchadnezzar

15:29

@user153330 Heya, just back from Africa

user153330

@N3buchadnezzar what were you doing in africa? : o which country btw?

N3buchadnezzar

Sitting on the train back now. Been traveling for almost 24 hours :p

@user153330 Zanzibar (Tanzania), how are you btw?

user153330

@N3buchadnezzar great for the moment

user159870

Hello =) We have an equation of degree 3 in a field K. Can this equation have only two roots in K?

A Beautiful Mind

@N3buchadnezzar For me, travelling is a waste of time and money. =)

N3buchadnezzar

15:33

@user153330 Me too, writing on the train is always fin

*fun

A Beautiful Mind

@N3buchadnezzar Are you going to be a mathematician?

N3buchadnezzar

@user153330 Me too, writing on the train is always fin

*fun

@ABeautifulMind Huh?

@ABeautifulMind Meh :p

user153330

@N3buchadnezzar it must be a very comfortable train then :p

A Beautiful Mind

@N3buchadnezzar Then what will you do when you graduate?

N3buchadnezzar

@ABeautifulMind Start working, earn money, be happy :p

@user153330 It is rough as a cactus bottom

A Beautiful Mind

15:37

@N3buchadnezzar OK. I can no longer be happy in my country.

user153330

@N3buchadnezzar lol

@ABeautifulMind change the country

A Beautiful Mind

@user153330 So why did you ask me for the book recommendation?

N3buchadnezzar

@user153330 :p

A Beautiful Mind

@N3buchadnezzar Your hotel?

user153330

@N3buchadnezzar so you were climbing those trees?

@ABeautifulMind i don't see the relation

A Beautiful Mind

15:40

@user153330 There is no relation. We are just making conversation.

user153330

@ABeautifulMind what is the relatioon between "book recommandation" and changing the country

A Beautiful Mind

@user153330 I said there is no relation.

user153330

@ABeautifulMind okay, i asked thta since you are knowledgeable in that field

A Beautiful Mind

@user153330 It's just weird to me, since you weren't asking about a specific field.

N3buchadnezzar

@ABeautifulMind Yeah, pretty nice. Traveling can be fun, if it is on one's own merits.

A Beautiful Mind

15:42

@N3buchadnezzar Have you found a girl?

N3buchadnezzar

@user153330 There were actually coconuts in them, apperntly they had quite a few incidents in the "coconut season"

@ABeautifulMind No meat, no pudding ;)

A Beautiful Mind

@N3buchadnezzar What incidents?

N3buchadnezzar

@ABeautifulMind No meat, no pudding ;)

A Beautiful Mind

@N3buchadnezzar Don't you already have the meat?

N3buchadnezzar

@ABeautifulMind Slow net on the train, yeah I guess you could say I have half of it.

@ABeautifulMind You know people getting hit by coconuts

A Beautiful Mind

15:44

@N3buchadnezzar You don't need meat. You just need a banana.

user153330

@ABeautifulMind and a mango

A Beautiful Mind

@user153330 LOL

N3buchadnezzar

Sante sana squash banana

user159870

16:02

Could someone help me at this:

We have an equation of degree 3 in a field K. Can this equation have only two roots in K?

?

Joe Stavitsky

16:17

Could someone explain this to me, as in why the x+2 is not multiplied by -1? goo.gl/u2xVO0

Chris's sis

@robjohn I'm preparing to upload the problem L+3. Please check it when you're back.

user91500

16:34

@JoeStavitsky $-\frac1{x+2}=\frac1{-(x+2)}$

Chris's sis

16:48

@robjohn I think I used "right" word instead of "left" word. I make the correction and upload again.

Mary Star

Hello!! When we have that $$f(4)=f(-4)=7.5 \\ f(-3)=f(3)=2.25 \\ f(-2)=f(2)=-1.5 \\ f(-1)=f(1)=-3.75 \\ f(0)=-4.5$$ how can we find the function f??

Kevin Driscoll

@MaryStar Do you know that the function is a polynomial?

Chris's sis

@robjohn done

Mary Star

@KevinDriscoll It is a parabola.

Kevin Driscoll

@MaryStar Well then we know an important detail, that $f$ can be written as $a x^2 + bx +c$

@MaryStar So how are these values you've written down related to the function I just wrote out?

Mary Star

17:06

@KevinDriscoll So, using the values I have written above we have to find the values of $a, b, c$, right??

Kevin Driscoll

@marystar Indeed

Samuel Yusim

@user159870: assume that a polynomial in K has degree 3 and exactly 2 roots. Then it factors into two linear factors and something else

in K that is

er, K[x]

say we have (x-a)(x-b)g for some g whose form we don't know

well, (x-a) and (x-b) both have degree 1, and we know that deg x-a + deg x-b + deg g = 3

so deg g = 1

meaning it's linear, a contradiction

since then g can be written as (ignoring some constant factor) x-c for some c in K

Ted Shifrin

@user153330: I am extremely fond of applications, so no anger for that here. Besides, there's differential geometry in one of the frames :P

hi @Kevin @Chris'ssis @MaryStar

Chris's sis

@TedShifrin Hello. How are you doing?

Kevin Driscoll

HOwdy @Ted

A Beautiful Mind

17:16

Hello @TedShifrin.

Ted Shifrin

Quite well, thanks, @Chris'ssis. You buried in integrals?

hi @Jasper

A Beautiful Mind

@TedShifrin Whatever I change my name to, you always use @jasper, lol.

Chris's sis

@TedShifrin Not really. I'm working on limits with nested radicals (from my research). :-)

Ted Shifrin

Yes, @Jasper. I'm an old dog.

BBIAB

Deep

Mi

*Hi

Wow, off to a good start.

Samuel Yusim

17:22

hi

Deep

How are you guys?

Samuel Yusim

the usual basically. so like, just doing assignment after assignment

you?

Deep

I'm great :D

I need a hand with naming a shape...

Is that on topic here?

Samuel Yusim

I'd guess it probably is

Mike Miller

Morning, @Ted.

Deep

17:25

Well, Imagine a torus, made up of trepezoids, in a hexagonal shape

Like this:

THere

Mike Miller

I would probably call that a toroidal polyhedon with 24 quadrilateral faces.

Deep

Now imagine two hexagons covering the hole, top and battom,

*bottom

making it a flat shape, well, idk if that even makes sense.

Mike Miller

Oh, I see.

I understand what you mean.

I don't know what I'd call such a thing. I'd probably just describe it.

Joe Stavitsky

@user91500 ty

Samuel Yusim

so it's got 2 hexagonal faces and 12 4-sided ones?

Deep

17:28

Yup

Kevin Driscoll

ya its an irregular polyhedron with 14 faces so unlikely to have a name

Deep

Oh ok

user91500

@JoeStavitsky yw

Samuel Yusim

name it whatever you want

Mike Miller

The thing you're building is homeomorphic to a 2-sphere, if that helps.

Samuel Yusim

17:28

that's what I'd do

Deep

It's the shape of a building in one of my short stories

and I wanted it to be accurate

But thanks :D

Samuel Yusim

well be aware of your audience, right

Kevin Driscoll

I think a jewler is more likely to hav a name for that shape than a mathematician

Mike Miller

The reader would definitely appreciate a description rather than a mathematical name.

Samuel Yusim

if you didn't know the terminology what's the likelihood they will

Deep

17:30

Fair point...

Samuel Yusim

in other news linear programming is an unexpectedly cool subject

Mary Star

Ok @KevinDriscoll Thank you!! :-)

Hello @TedShifrin :-)

user159870

So @SamuelYusim either the polynomial has 1 root or 3 roots. Correct?

Samuel Yusim

nope, it could also have 0

user159870

17:45

Oh ok! So the possible number of roots are 0,1,3. Thanks @SamuelYusim !

Samuel Yusim

no problemo

crl

18:32

f(x) =
\begin{cases}
x, & \text{if }x \in [-180,180] \\
x+360, & \text{if }x \in [-360,-180] \\
x-360, & \text{if }x \in [180,360]
\end{cases}

Is there a simple formula, without cases, for this function?

I'm thinking of something with modulus

Hippalectryon

@crl There is, but it's pretty much the same ...

@crl Something like $f(x)=x\cdot\dfrac{\max(0,180-x)+1}{\max(0,180-x)+1}+\dots$

Well, not that one, which doesn't work. But kind of.

You get the idea.

crl

@Hippalectryon I was thinking of $f(x) = ((x+180) \% 360 ) - 180$

Hippalectryon

That wouldn't work.

Kevin Driscoll

mod only returns positive numbers, doesnt it?

Hippalectryon

Modulos would still give you increasing fonctions, not constants.

crl

18:45

sorry edited, and % is modulus I didn't find the mathjax command for it

@KevinDriscoll yes

Kevin Driscoll

@crl Your original function jumps from -180 to +180 at x=-180 but your mod version doesnt do that

@crl This looks like a sawtootch function though, so you could reresent it as the Fourier Transform of a single function

without cases

I think

Or equivalently, use a fourier series

crl

ok I think my solution was wrong too

weird, the modulus can take negative values: fooplot.com/…

Kevin Driscoll

@crl I think that depends on how you implement the modulus functions

that way its defined, it should be positive definite, I think

crl

@KevinDriscoll indeed, the plotter uses the truncated division, not theEuclidean one en.wikipedia.org/wiki/Modulo_operation

hmm I really need a formula because the input domain might be larger than [-360, 360]

Kevin Driscoll

19:10

@crl If you compute the fourier series that will give it to you over the whole domain

I mean all of $\mathbb{R}$ because its periodic

Vrouvrou

19:37

Hello, I have a small question i have a topological space $(\N,\tau)$ where $\tau=\{\emptyset,,\mathbb{N},\mathbb{N}^*, \{A_n\}_{n\in\mathbb{N^*}}\}$, $A_n=\{1,2,....,n\}$ and we consider the set $A=\{2n, n\in \mathbb{N}^*\}$ I want to find $\overline{A}$ and $\overset{º}{A}$ and $A'$

I found $\overline{A}=\mathbb{N}\setminus\{1\}, A'=\mathbb{N}\setminus\{1,2\}, \overset{º}{A}=\emptyset, Fr(A)= \overline{A}$ is it true ?

tcp

hello, i am computing p(a) = $$ \sum_b\sum_c\sum_d\sum_e\sum_f\phi(a,b)*\phi(a,c)*\phi(b,d)*\phi(c,e)*\phi(b,e,f‌)$$. What is the computational complexity if I naively sum it up given each variable can take r values? Ans given is r^6.

Hippalectryon

@Vrouvrou What is $Fr$ ?

@tcp Mind explaining your notations ? What's, for instance, the complexity of calling once $\phi(x,y)$ ?

Vrouvrou

19:53

@Hippalectryon the boundary

Hippalectryon

@Vrouvrou What's the difference between $boundary(A)$ and $(\bar A)$ then ? To me, it means the same.

tcp

It is a negative potential function used for calculating marginal probability. Author wants to stress more on the way multiple summations should be carried out to reduce computational complexity than the function. In his own words "Naively, if each of these sums is applied to summand involving six variables computational complexity scales as $$r^6$$ "

Vrouvrou

@Hippalectryon it is $\overline{A}\setminus \overset{º}{A}$

Hippalectryon

@Vrouvrou Oh you're right, I'm mistaken :)

Pedro Tamaroff

20:07

@TedShifrin Hallo.

Ted Shifrin

hallo @Pedro

Lord_Farin

Hello, @Pedro and @Ted.

Ted Shifrin

hi @Lord

crl

@Hippalectryon la frontière et l'adhérence :)

Lord_Farin

How are you doing?

Hippalectryon

20:10

@crl En effet, j'avais confondu les notations :-)

crl

I think there are cases where they are different, but I may be wrong, it's so far away

Hippalectryon

@Lord_Farin Hoi, Flour Lord

Ted Shifrin

Les jeunes doivent ne pas confondre :P

crl

tout à fait

Lord_Farin

@Hippalectryon Hello, my Nilpferd :).

crl

20:11

soy un viejo, ahora, 29

Hippalectryon

@Lord_Farin Hehe

Ted Shifrin

was ist ein Nilpferd?

Lord_Farin

@TedShifrin You would describe it as "hippopotamus".

Ted Shifrin

ah :)

hipp_o_ au lieu d'hipp_a_ :D

Hippalectryon

@TedShifrin I heard you got attacked by a wild baby hippa

Ted Shifrin

20:14

You should make him a stronger leash, @Hippa.

2

Hippalectryon

silently laughts

Ted Shifrin

you're rarely silent about anything, @Hippa.

So, @Pedro, now that you've abandoned cats, what are you working on?

Vrouvrou

Hello, please i have three sets $X\subset Y\subset Z$ what it means $X,Y,Z$ are homotopically equivalent ?

Pedro Tamaroff

@TedShifrin I have to prepare two final exams. I kinda finished writing some notes on the structure theorem for modules over PIDs, and decided to read some more of Ireland and Rosen's book.

Ted Shifrin

ah, reverting to your old number theory ways ... good, get those final exams over with :)

Lord_Farin

20:17

@Vrouvrou Tried WikiPedia?

Pedro Tamaroff

@TedShifrin I do want to continue with Remmert's second volume too.

Since I have to prepare complex analysis, too.

Ted Shifrin

yes, good, so you can learn that last problem on my exam :P

evinda

@DanielFischer I am looking at the following exercise:
Assume that at the nodes of a 2-3 tree, the following keys are saved (in an increasing order): $3,6,9,15,18,21,24, 27, 30, 33, 36$.

It is also given that the root is a 2-node that contains the number $12$.

Draw the tree.

PS: It is not required to make so many insertions as the above keys in an initially empty 2-3 tree. It is just required to draw only one tree that is a 2-3 tree and that contains the above keys at its nodes(which you have to decide if they should be 2-nodes or 3-nodes).

Could you tell me if it is right?

Pedro Tamaroff

Hehe, yes.

I've already forgotten what it said.

Daniel Fischer

@evinda I know nothing about 2-3 trees.

evinda

20:21

A ok @DanielFischer

Ted Shifrin

I'm the forgetful one, @Pedro.

It was a power series expansion, and you were supposed to prove the function took on every value infinitely often, @Pedro.

hi @DanielF

Pedro Tamaroff

@TedShifrin Ah, OK.

Daniel Fischer

Hi @Ted.

tcp

20:35

@v

Vrouvrou

@Lord_Farin it means that there existe two homotopy $F_1:[0,1]\times X\rightarrow Y$ such that $F_1(0,x)=f\circ g(x)$ and $F_1(1,x)=id_{Y} (u)$ right ?

tcp

@Vrouvrou can u help me?

Vrouvrou

@tcp i don't know what is your problem ?

tcp

i am computing p(a) = $$ \sum_b\sum_c\sum_d\sum_e\sum_f\phi(a,b)*\phi(a,c)*\phi(b,d)*\phi(c,e)*\phi(b,e,f‌‌)$$. What is the computational complexity if I naively sum it up given each variable can take r values

Lord_Farin

@Vrouvrou There must exist homotopies $H_X$ between $g \circ f$ and $id_X$ and $H_Y$ between $f \circ g$ and $id_Y$.

Vrouvrou

20:40

@Lord_Farin for the first it is right ?

Lord_Farin

I don't understand you :(.

Vrouvrou

@tcp sorry i can't help you

tcp

is there a chat room for probability folks?

Vrouvrou

is $H_Y=F_1$ @Lord_Farin ?

Modded Bear

why did this get a downvote? math.stackexchange.com/questions/1119105/multiples-of-3-and-5/…

Vrouvrou

20:42

@ModdedBear +1

Lord_Farin

@Vrouvrou Yes, except that you wrote the domain of $F_1$ is $[0,1]\times X$, and supplied arguments indicating the same.

Modded Bear

@Vrouvrou thanks, although I don't know why it would get downvoted

Lord_Farin

@ModdedBear Life sucks.

Modded Bear

fair enough

Vrouvrou

@Lord_Farin what must be the domain of $F_1$ ?

Lord_Farin

20:44

Well, if it is to be a homotopy involving $id_Y$, it ought to be $F_1: [0,1] \times Y \to Y$, right?

Chris's sis

@robjohn how would you characterize that nested radical limit? It's created by me. I personally think it would be a nice problem for my book.

Vrouvrou

oh ok

@Lord_Farin $H_X$ must be defined from $[0,1]\times X\rightarrow X$ right ?

Lord_Farin

@Vrouvrou Indeed.

Vrouvrou

thank you

Lord_Farin

You're welcome :).

Cortizol

20:53

Does anybody know some good book (except Matrix Analysis from Rajendra Bhatia) that deals with unitary invariant norm and their relation with antisymmetric tensors product on Hilbert spaces?

Kevin Driscoll

This sounds like physics!

Cortizol

Well, I don't know physics. Yes, as far I know physicists are working with antysimmetric tensor product, but that is not my main interest for studing, more p-norm, unitary invariant norm and some inequalities about that (oh, my splendid English)

Vrouvrou

@Lord_Farin please even if $Y\subset X$ $H_Y: [0,1]\times Y\rightarrow Y$ ?

Lord_Farin

21:08

@Vrouvrou Yes. It's the general definition, so it's best to stick to it, even if $Y$ lies within $X$ (so that $H_Y$ has a natural interpretation with codomain $X$ as well).

This way you prevent errors, e.g. when you don't know $Y$ is a subset.

Vrouvrou

Please if $Y\subset X$ is this homotopy give me a deformation or any topological information about this sets ?

@Lord_Farin

Lord_Farin

@Vrouvrou Well, I think it tells you that the restriction of $f$ to $Y$ is homotopic to the identity $Y$. (Presuming that $g$ is the inclusion.)

But it's been a while since I studied homotopies properly, so I may not be the most authoritative person you could ask.

Lord_Farin

21:25

Interestingly, the views on my meta thread seem to explode after it has been locked.

Chris's sis

Oooo, I just came across another amazing nested radical.

Lord_Farin

@Chris'ssis Nested radicals are awesome.

Chris's sis

@Lord_Farin Yeah, especially when they come from personal research. :-)

Lord_Farin

Cool :).

Chris's sis

@Lord_Farin :D

user153330

21:29

hey @Chris'ssis

Chris's sis

@user153330 Hello

user153330

@Chris'ssis so how are you? you seem to be as creative as always : )

Chris's sis

@Lord_Farin Every time I find something very nice I feel myself closer and closer to Ramanujan. My book will also be dedicated to Ramanujan.

Lord_Farin

@Chris'ssis :)

user153330

@Chris'ssis and to hippa...

Chris's sis

21:31

@user153330 Hello. Yes, indeed. :-)

@user153330 haha, yeap ;)

user153330

4

Ramanewbie

@user153330 has @ted seen it yet ?

Chris's sis

@user153330 hahahaha, mathemafu**ers :-))))

user153330

@Ramanewbie yep, you were right, he isn't the killer

@Chris'ssis lmao

Ramanewbie

@user153330 you mean ted isn't the killer ?

user153330

21:36

@Ramanewbie yup

Ramanewbie

@user153330 he's not here, but I don't know if he'ld be happy hearing that -_-

Vrouvrou

Why downvote for this: mathoverflow.net/questions/194679/…

if someone know the answer please give it

Ramanewbie

@vrouvrou how did, d'you know ?

Kevin Driscoll

@Vrouvrou My guess is that if you know the equation is true then the question isn't research level

ie you must have read it in some book or paper or something

but thats just a guess

Vrouvrou

i read it in a an application in a paper

but i must prove it

and i don't find the proof in any book

Kevin Driscoll

21:42

I figured it was something like that. Im no mathoverflow expert.

I would add the reference though so other can see the stated equality in context

Vrouvrou

as you want

Kevin Driscoll

@Vrouvrou Iw would also answer Fernando's question. You know the equality holds because you read it in a paper.

user153330

@Ramanewbie i think he's the one who was killed :/

Vrouvrou

@KevinDriscoll i added the ref

user153330

@NajibIdrissi who is cécile thiébaut for you?

Chris's sis

21:57

@Lord_Farin in the memory of Ramanujan

Lord_Farin

Should the brackets stop before the second $+$?

Chris's sis

@Lord_Farin No.

Lord_Farin

@Chris'ssis Hm, interesting.

Transcript for

$Mathematics$ Mathematics