Oh ... Totally not understood. You need to be explicit.

@MikeMiller ok, sure.

Hence my discussion of diagonals.

Generally, for things that aren't, say, countable, one wants to think of a continuous action rather than what you're talking about (which is a continuous action of the discrete version of the group).

e.g., $S^1$.

then you agree about the SES of cech fundamental groups, @Mike?

Now I might believe it ...

No, I don't know anything about Cech fundamental groups.

@TedShifrin I guess that's because in French it's explicit :) i'll fix that

i duncare about S^1 @Mike

Great! I don't care about what you're thinking about either.

@evinda Is $p$ fixed, or is it a parameter? Well, ought to be fixed, since otherwise the running time would need to depend on $p$ too. Basically, you modify quicksort to get the m-p-th smallest and m+p-th smallest elements in their places, and the elements whose value is between in the subarray with indices m-p to m+p. Then sort that subarray and find where exactly the p elements closest to the median are.

yes, if you say the standard basis vectors for the space of matrices, then we understand, @Hippa.

@MikeMiller are you prepared to see my proof for cech fundamental groups?

@TedShifrin Thanks. Do you know how to solve it now ?

I'm not going to read it, no.

why, @Mike :(

you so mean

Not quite, but I see the diagonal case, @Hippa.

Ok, time to get ready for my dinner guests ...

@BalarkaSen It's assuredly not something I like to think about. If you want to check it, carefully go through it and justify every step with full detail. Make sure at every step of the way you're not using the words 'trivial' or 'obvious' or anything similar.

@DanielFischer I haven't understood it... :/ Do I have to change the medianOfMedians algorithm? If so, how? :/

@MikeMiller I think I have only a single clarification to make : If $p :X \to Y$ is a covering map, $U$ is an open cover of $X$, $p(U)$ an open cover of $Y$, then there is a covering map $p' : \mathcal{N}(U) \to \mathcal{N}(p(U))$ of abstract simplicial complexes, right?

I don't know.

You're the one who knows all the relevant definitions and theorems here.

:(

I find it intuitively to be true, but not sure.

N(U) is the nerve of U by the way

Do you at least believe it, @Mike?

I have not thought enough about such things to have an opinion either way.

OK sigh

Sorry if I bothered you.

Nah.

@AlecTeal Could you take a look at this exercise: math.stackexchange.com/questions/1065465/… ?

I guess that short exact sequence also works if your group G is disconnected @Mike.

@BalarkaSen Yeah, it works for any group with $\pi_2(G) = 0$. Totally disconnected stuff has that; Lie groups have that.

Hmm. Your claim looks interesting. Why does it work for any group with \pi_2(G) = 0?

Looks nontrivial.

@evinda sure

From any fibration $F \hookrightarrow E \to B$, there's a long exact sequence in homotopy groups $$\dots \rightarrow \pi_n(F) \to \pi_n(E) \to \pi_n(B) \to \pi_{n-1}(F) \to \dots$$ In the situation we've described, there's a fibration $G \to X \to X/G$. So if $\pi_2(G) = 0$ and $X$ is connected (aka, $\pi_0(X) = 0$), then we get your desired sequence.

@evinda you know about graph-viz right?

Oh! It can be derived from the long exact sequence?

@AlecTeal What is it? :/

Yes.

That's pretty cool.

@evinda drawing graphs is not human work, so for one courework module we had to create an ERROR TOLERANT parser - that is a parser that gives useful errors and resumes parsing, cool right?

@AlecTeal So can we create with this program graphs?

@evinda That's not the only way to do it, but it's an easy way to modify median of medians and quicksort to do the desired thing. But I would say it would be better if you discuss these things with your fellow students or professors/TAs/tutors in real life, that way one can better go into the details that need going into.

It's much faster to write on paper or a blackboard too, and things can be explained while writing. And implement and run the algorithms to understand how they work, then you will be able to modify them when you are asked for an algorithm doing something slightly different.

@evinda I'm trying to upload an image

Graphviz! You output a file like "digraph G { a->b [label="Hello"]; c; d; d->a; }"

and it draws it

Graph viz is cool stuff @AlecTeal

Used it once.

Okay

@evinda there's an old wiring diagram. Anyway to see what your program is doing, use graphviz

@DanielFischer It's a homowork, so I cannot discuss it with my professor or my fellow students... Could you maybe explain me how we could modify one of these algorithms?

@AlecTeal What I could I see using this program? :/

Your algorithm's output at each step, running by hand is really error prone

Use Python, it's an invaluable tool

@evinda It's a homework, you're not allowed to discuss it with your fellow students... why do you think you're allowed to discuss it with strangers online?

@MikeMiller if either @evinda or @MaryStar show effort I will reward it

@MikeMiller I like @DanielFischers explanations and after reading them I understand the staff better...

But yeah @evinda use a bit of Python and a bit of graphviz, it will help you A LOT

You could, maybe, I dunno, listen to your prof's lectures to understand the "staff" better, @evinda?

@BalarkaSen We don't do exercises with the professor in class....

@BalarkaSen don't join in, seeking help is not a bad thing, but expecting others to do it for you and baiting them with "I like it when you give me good descriptive answers I can reword" is bad.

He gives good explanations, but if you're not allowed to discuss this with your instructor or classmates, I can't believe you're allowed to discuss it with anyone. This is academic dishonesty. Your work should be your own, not Daniel's.

You can discuss mental problems with me though, not math problems.

@MikeMiller they wouldn't set such an unenforceable task, perhaps @evinda just wants a fresh input.

WTF is wrong with you today?

Yeah, they would. One is supposed to trust their students not to cheat. It's not the instructor's job to avoid cheating, it's the student's.

Yeah in opposite land.

"Do this exam as homework, in for next week, remember no cheating guys!"

I understand that the CrazyTown university uses that system, 90% of the final mark.

Lots of moderators flying around the chatroom today.

I didn't mean that the prof told us that it is not allowed to discuss the exercises with the classmates but I usually don't ask my classmates for help at the exercises...

I know @evinda, @MikeMiller was just being a pedant - which isn't a bad or nasty word in case some tool decides to flag this :P

@evinda You don't necessarily ask for help with the exercises. Just discuss the topics of the lectures with them. Discussing that makes you - and them - understand the material better. Then you will only need a small nudge to do the exercises yourself.

@SamWhited Flags flying low today?

I wonder what was flagged

Me too

I wonder why. Didn't notice anything truly offensive.

Good time of day all

@DanielFischer My classmates at this subject are all at an higher semester and they haven't passed this subject yet and they don't really occupy with this.... nevermind...

why does math.uga reminds me of university of uganda whenever i open up pete clark's notes? :P

@SamWhited with maths there's a lack of good questions to do, because a lot of questions are along the same lines (just with different numbers maybe) - so "proof of work" is expected. MaryStar for example, slew of questions with no effort, just copied, so not likely to get an answer.

And meanwhile people like me post very few questions because our standards are so high...

"solve this equation" is still a sensible question title. "i need halp ASAP!!!!1!" isn't.

and that's what you get most of the time in MSE

The best one I've found was a picture of a project that said in the description, "I need this by tomorrow."

LEL @teadawg1337

@evinda Does that mean you don't know them well enough to discuss things with them? That would be unfortunate because really face-to-face talking works tons better than internet-to-and-fro.

@DanielFischer No, I don't know them..

OK, I need to run.

Dead of a night in here.

@evinda :( Any chance you might get to know a couple of them?

@DanielFischer In one week the semester ends...

@evinda Okay, that's a bit late to get to know them.

Wait, when are hats?

Anyway, @evinda, the partition step of quicksort puts the pivot into the correct position, and all smaller elements before, all larger elements behind the pivot. We want to find what would occupy slots $m/2-p$ to $m/2+p$ if the entire array were sorted.

Now, if the pivot happened to be the $m/2+p$-th element of the array, you see that after the first partition step, we could completely ignore the part of the array behind that, right?

The outlook web app is truly awful

TRULY

@AlecTeal Hear, hear!

@DanielFischer What do you symbolize with $m$ ?

@evinda The length of the array.

@DanielFischer A ok... And why do we want to find what would occupy slots $m/2-p$ to $m/2+p$?

@evinda We want the $p$ elements closest to the median. They are (after sorting) somewhere in these places, and could be any $p$ consecutive elements in that range.

So we need to know how that range looks after sorting. But we don't need to know how anything outside that range looks after sorting.

(And as an aside, if $p > m/2$, we cap the bounds to $0$ and $m-1$, since that is the entire array.)

@DanielFischer Do you have an idea on my latest question ?

@Hippalectryon $$\int_0^{\infty} \frac{(1+a x)^{-p}-(1+b x)^{-q}}{x} \ dx$$

@Hippalectryon Try for $n = 2$ and $n = 3$, that might give a clue.

@robjohn have you met before the integral above?

@DanielFischer I did try :/ but even for $n=3$ I didn't manage to solve it

@Chris'ssis $a,b,q$ ranging over .. ?

@Hippalectryon But $n = 2$ is possible, I presume?

@Hippalectryon You need to figure out ...

@DanielFischer I didn't manage that one either :/

@Hippalectryon say $a,b,p,q>0$

@Hippalectryon How do orthogonal $2\times 2$ matrices look?

@DanielFischer I know their form over $\mathbb{R}^2$ but I can't think of a general form

@DanielFischer If $m$ is even, will the median element be at the position m/2? And if it's odd at (m+1)/2?

@evinda Not quite. If $m$ is even, the median is the mean of the elements at places $m/2-1$ and $m/2$, and for odd $m$, it's the element at index $(m-1)/2$, all after sorting.

@DanielFischer So, do we have to call the partition and not to set x=A[r] but x=A[m/2+p]?

@evinda Sorry, I don't understand what you're asking.

@Hippalectryon I'm done in one line. Happily!!! (I simply had luck)

This edit did not improve the title much

@Chris'ssis 0_o one line

@Behaviour It was probably to ping the question to the front page

@Hippalectryon Maybe you don't know, but that one comes from Ramanujan. I'd be curious to see his own proof.

@evinda Either that, or we have to swap the pivot to A[r] before calling partition. As is, that would not be able to guarantee the desired complexity.

But, that looks wrong. Not at all like quicksort's partition. Where is that from?

@DanielFischer That's from my book...

@DanielFischer So is it wrong? Should I send it as a picture?

@evinda Not wrong in the sense that it doesn't do what it should - provided the indentation is right in the book.

But wrong in the sense that Hoare's algorithm is different, more efficient (constant factors, not computational complexity, but the constant factors matter).

And people wonder why software is so slow nowadays if even algorithm books don't care about efficiency.

I didn't know I wondered @DanielF

@TedShifrin How do you solve the diagonal case ?

There are orthogonal matrices with lots of $1$'s and $-1$'s on the diagonal @Hippa.

@TedShifrin Maybe not everybody wonders.

I've been cooking, so I haven't been working on math ... Just stopping by.

@TedShifrin I still don't see how a LC of two orth matrices gives you a matrice with a $1$ somewhere on the diagonal and $0$ elsewhere

So, @DanielF, do all the new moderators want us to to turn into a homework-processing plant?

Think about what I just said, @Hippa.

@TedShifrin Oh wait I'm stupid. They just need to both have $\frac{1}2$ at the spot where it will make $1$, and differing signs elsewhere

Nah, you just typed before you thought.

@TedShifrin Depends on who gets elected.

(See, @Alec, I can be nice to @Hippa ... once a year.)

Well, the matrices need to be orthogonal, so the column vectors need to be unit vectors, but you can use your constants to scale appropriately, @Hippa.

That's what I meant :) That doesn't solve the other cases though

Is Brian Scott running for mod, @DanielF?

Well, @Hippa, with cleverness, it might.

I haven't had time to play.

@TedShifrin No, he isn't.

@TedShifrin >.> thanks for the non-advice

You're welcome, @Hippa. Hey, you're farther along than you had been.

@Hippa: Why can't we do the exact same thing in any slot?

heya @Sawarnik

hello @TedShifrin :)

@TedShifrin Because when there is more than one coefficient per line/column, making the matrices orthogonal becomes difficult

I don't believe you.

@evinda Except for the pivot = 4, which is a dummy line. Yes, that's the real deal.

@DanielFischer Do you know how many mods are to be selected in this election?

Note that there are also unit vectors with precisely one non-zero entry, @Hippa.

@Sawarnik My name isn't DanielFischer, but the answer is 3.

I thought just one, @Sawarnik.

Oh, wow, three?

@TedShifrin Uh ? How does that help ?

It helps a lot, @Hippa.

Take a vector with a $1$ in the $ij$-slot as one of the columns of both matrices.

@TedShifrin Willie Wong announced his pending resignation, and there will be one moderator more.

Willie was the one I knew about, I guess.

Who is the other resignator?

@Chris'ssis I don't know if in that exact form, but it looks similar to others I have encountered.

heya @robjohn

@TedShifrin Probably Alex Becker, hasn't been active for a while.

@TedShifrin howdy

wow, haven't seen him at all in ages, @DanielF

@robjohn It looks like a Frullani integral. Well, it's more than that, it's the generalized Frullani integral obtained by Ramanujan.

surmises from @Hippa's silence that he's figuring it out now

@TedShifrin O_o wait, what happens if I put a $1$ on position $i,j$ of each matrix, then fill out with $\pm1$ (differing signs on each matrix) on the remaining positions so that there is exactly one $\pm1$ per line/column ? Would that work ?

@TedShifrin I was typing

yes, or any other completion to an orthonormal basis would work, too

U_u I'm amazed no one on main had answered my question

See, I did even so ... :P

Thanks

Post a solution and give us both credit :)

Hehe

I've moderated on gaming communities before, and you wouldn't believe how many times I've been asked whether I get paid for it. Apparently, that's a common thing here too.

I do lots of things in my regular job that very few other people do (if any at all), and I've never gotten paid extra :P

@Chris'ssis does it not depend on $a$ or $b$?

@evinda No, the indices $m/2+p$ and $m/2-p$ (perhaps plus/minus one) are not pertinent for the partitioning step, only for the recursive calls, to decide whether both shall be made, or only one, and if one, which.

@robjohn $$\int_0^{\infty} \frac{(1+a x)^{-p}-(1+b x)^{-q}}{x} \ dx=\psi(q)-\psi(p)+\log\left(\frac{b}{a}\right)$$

@DanielFischer A ok.. But after having called PARTITION, the array will not be sorted, or am I wrong?

@Chris'ssis Oh, yeah. I missed that it is dependent on $b/a$

@robjohn I think I know the integrals you had in mind when you asked that question. I'll show you when I write up my proof to this one. It's a terribly nice question (integral).

@evinda It won't be sorted, but it will be partially sorted, in that elements $\leqslant \text{pivot}$ are before the pivot position and elements $> \text{pivot}$ are after.

Now, @evinda, if you select the pivot with median of medians, it will be not too far from the middle of the array.

I've been reading a lot about the beta function today. When is it usually taught in college mathematics?

@DanielFischer So you mean that the function hoare should call the fuction medianOfMedians?

And if you then partition the part before the pivot from the first round and the part after, you have three elements that served as pivots in the partitionings, one at roughly $m/4$, one around $m/2$, and one around $3m/4$. And all elements whose value is between the two outer pivots are then between them.

@evinda Either that, or the function that calls hoare should do it and swap the pivot in the place where hoare expects it.

@teadawg1337 Usually? Never.

@TedShifrin Is that ok ?

The beta and gamma functions were mentioned briefly in a course I took titled 'advanced calculus'; we basically noted that there was a smooth extension of the function $n \mapsto (n-1)!$ to the reals. I never saw them again.

Ughhh........

Again, with someone beating me out on an edit.......

@evinda More or less. hoare above took only three arguments, you pass four here, additionally the position of the pivot. If you modify hoare to take that fourth argument, it's fine.

@MikeMiller Huh, interesting....

@DanielFischer Nice :) And now what cases do we have to distinguish? :/

@evinda The next trick is that we control the recursion, and skip the unnecessary work. And the function should not be called Quicksort, since we're not sorting the entire array.

@evinda Next, we need to exactly find the start and end of the part of the array we want to actually have sorted.

@DanielFischer So now the function doesn't call itself but we have to call an other function?

@evinda Slowly, slowly. Let me finish typing something else first.

@DanielFischer A ok, I am sorry!!!!

@Chris'ssis I would start with $$\int_0^\infty\frac{(1+ax)^{-p}}{x^t}\mathrm{d}x =\frac{a^{t-1}}{1-t}\frac{\Gamma(2-t)\Gamma(p+t-1)}{\Gamma(p)}$$ for $t\lt1$. Subtract and let $t\to1^-$

@robjohn It should give the result. Did you check that with Mathematica?

Hey guys, I'm looking for a reference for the following theorem:

If $f,g$ are homogeneous polynomials in $k[x_0,\dots,x_k]$ of degree $n,m$ respectively, then $R_{x_0}(f,g)$ is homogeneous, of degree $nm$

@Chris'ssis No... just working on the limit now. This is very much like another integral I did on chat.

@robjohn Yeap, your way should definitely work. Nice approach.

Here $R_{x_0}$ stands for the resultant of $f,g$ viewed as polynomials in $k[x_1,\dots,x_n][x_0]$

If the array has $2k+1$ elements, the median will sit in position $k$ after sorting. We want $p$ elements, among them the median, and they are consecutive in the sorted array. So the earliest possibility is that we want the elements from index $k-(p-1)$ to index $k$, and the latest is that we want the elements from index $k$ to index $k+(p-1)$. So we need the part of the array from index $k-(p-1)$ to $k+(p-1)$ to cover all cases.

If the array has $2r$ elements, the two elements determining the median sit at positions $r-1$ and $r$ after sorting. The $p$ elements closest to the median - if $p > 1$ - necessarily include the two middle elements. (Or the choice is not unique, but then at least some admissible choices include both middle elements.) So we need the part of the array from positions $r-(p-1)$ to $(r-1)+(p-1)$.

Thus, whether the number of elements $m$ is odd or even, the relevant indices are low = (m/2)-(p-1) and high = (m-1)/2 + (p-1).

Now, @evinda, we use low and high to control the recursion.

If the partitioning (the call to hoare or the other partitioning implementation) places the pivot at index q, then we must compare q to low and high.

@Chris'ssis $$\lim_{t\to1^-}\left[\frac{a^{t-1}}{1-t}\frac{\Gamma(p+t-1)}{\Gamma(p)} -\frac1{1-t}\right] =-\psi(p)-\log(a)$$ That gives the result

If q-1 < low, then we don't need anything from the part of the array before the pivot position q, hence we skip the call partialQuickSort(Array, left, q-1). Similarly, if q+1 > high, we need nothing of the part after the pivot, hence we skip the call to partialQuickSort(Array,q+1,right), @evinda.

@DanielFischer But I thought that the elements before the pivot element are not sorted.. How can we begin from the index $k-(p-1)$ ?

@evinda No, they are not sorted, that's why we recur. The point is that we need only a part of the sorted array, hence we can omit some recursive calls and thus get the complexity down to $O(m)$.

@DanielFischer So don't we want the elements from index $k-(p-1)$ to index $k$ if the array was sorted?