Mathematics - 2017-09-05 (page 6 of 7)

Wildcard

21:01

@orlp Hmmm.

orlp

@LeakyNun I don't understand

Wildcard

@orlp Neither do I.

Leaky Nun

Because groups of order $p^2$ are abelian. — Qiaochu Yuan 9 mins ago

group theory is so beautiful

@orlp I mean, we connected the extremities and then used the smallest-distance protocol

Wildcard

In the $n=3$ case, if Alice has an $1$ to send, why not send that if she gets $\{1,3\}$? She only needs to punt to $3$ if the next bit in her message is not one she has available. This lets her transmit $\frac23$ bits per round on average. — Henning Makholm 2 mins ago

D'oh.

orlp

@LeakyNun no, we're talking about something else now

@Wildcard see my comment

Wildcard

21:05

That's even what I was alluding to earlier when I mentioned amount of noise.

orlp

it assumes information about the distribution of the information that we're transferring

what if I only want to transfer 1111111111111111111?

Wildcard

@orlp Still works.

The key is that 2/3 of the possible inputs contain your desired output, no matter what your desired output is.

orlp

oh right

it does still work

that solves $b(3)$ I'm fairly convinced

Wildcard

@orlp Yup.

orlp

and my intuition was correct that $1/3$ isn't optimal ;D

Wildcard

21:07

So now let's try the next one, $b(52)$. ;D

orlp

but that doesn't solve $b(n)$..

Wildcard

Let's try $b(4)$ and see if a pattern emerges.

@orlp applause

Actually, I think a broader generalization is necessary.

Call what we've solved $b(3,2)$

We can try $b(4,2)$ or $b(4,3)$.

And if we want to scale it up to the original question,

We'll need to count the solved case as $b(3,2,1)$

And the final case of interest is $b(52,5,4)$

So define $b(j,k,l)$ as a scheme with $j$ possible numbers, where a random choice of $k$ of those numbers (distinct) are passed to person A, who selects $l$ of them to pass to B. With $k \le j$ and $l \lt j$.

And the question can be further complicated (in the original) by allowing person A to choose a permutation of the $l$ chosen elements.

Wow, that's a very nontrivial question.

@orlp In $b(4,3,1)$ you can use 1, 2, and 3 to relay your messages. And if the one you need isn't present in the set of 3 you are given, send the number 4 as a no-op.

So only 1/4th of the time would the needed number be missing. (I think...right?)

orlp

yes, $b(n, n-1, 1) \geq 1 - \frac{1}{n}$.

Wildcard

But for $b(4,2,1)$ it's trickier.

@orlp Right.

For $b(4,2,1)$, a starting point (not necessarily optimal) would be to use two data channels and two no-op channels.

That way every possible set you receive is guaranteed to either have the number you need, or a no-op number (or both).

Which gives 1/2.

orlp

@Wildcard you'll have to forgive me, I have a cold, coming with a headache

so I think for tonight I end here and I'll see what answers come in

Wildcard

21:18

@orlp Mind if I edit in the more general case to the question?

With three parameters instead of one?

(I'll leave out the permutation part.)

orlp

kind of

I feel that's more of a followup question

once this case has been resolved

Wildcard

@orlp Fair enough.

orlp

if you broaden the scope of a question too much the answers will also broaden into uselessness generally

Wildcard

@orlp Right.

I think it's possible that adjusting a different parameter may be a better line of attack.

But that's okay. :)

orlp

so instead of an answer you'll get a link to a thesis from 1983 that in section 8.3 studies something similar, but not exactly the same, with notation that you've never seen before and is impossible to google :P

2

Wildcard

21:19

@orlp :P

I think $b(4,3,2)$ (with or without permutations allowed) is an entirely different type of question from $b(4,2,1)$.

@orlp Get better (drink lots of water). Thanks for an interesting discussion. :)

Leaky Nun

Let $A=[0,1]$. Let $x \sim y$ denote $x-y \in \Bbb Q$. Form a set $S$ of representatives from $A/\sim$. Choose a random number uniformly from $A$. What is the probability that the chosen number is in $S$?

@orlp

orlp

@LeakyNun it's not clear to me what ~ is

Alessandro Codenotti

Hi @Ted

Ted Shifrin

Hi @Alessandro

Leaky Nun

@orlp an equivalence relation

orlp

21:26

(and how do you typeset ~ in latex)?

Leaky Nun

@orlp \sim

Ted Shifrin

\sim

orlp

nope, still don't understand the question

Leaky Nun

@orlp do you know what an equivalence relation is?

orlp

yes

Leaky Nun

21:28

@orlp and the relation between equivalence relation and partition?

Ted Shifrin

Hmm, that's an interesting question, @Leaky.

Leaky Nun

@TedShifrin it's a puzzle for orlp :P (anyone with any knowledge of measure theory would know the answer)

orlp

@LeakyNun no

it's also not clear with me what you mean with $x - y \in \mathbb{Q}$

Ted Shifrin

I have knowledge of measure theory.

$\pi/4$ is equivalent to $\pi/4 + q$ for any rational number $q$, @orlp

orlp

is that saying that the relation $\sim$ holds for numbers $x$, $y$ if their difference is rational?

Leaky Nun

21:30

@orlp yes

and then we group the related numbers into boxes

and choose one number from each box to form the set $S$

orlp

ah ok

Ted Shifrin

Well explained, @Leaky.

Alessandro Codenotti

@TedShifrin Is that actually a well defined question?

Leaky Nun

@AlessandroCodenotti shh.

orlp

I feel that in some cases the selection process matters though

Ted Shifrin

21:31

I have no issues with the axiom of choice, @Alessandro.

Leaky Nun

@TedShifrin thanks.

@TedShifrin it isn't choice that is problematic.

orlp

consider a relation $R$ that relates consecutive even/odd numbers

Leaky Nun

@orlp $A$ contains the numbers from $0$ to $1$

Alessandro Codenotti

@TedShifrin That's not my problem here, but I don't think there's a reasonable probability space for which this set is an event

orlp

then $\mathbb{N} / R$ can have an arbitrary amount of even numbers

Ted Shifrin

21:32

Well, it certainly isn't counting measure :P

orlp

but I'll assume good faith and that it doesn't matter here

Leaky Nun

@orlp right, it doesn't matter here. The axiom of choice is not the problematic element here.

Ted Shifrin

Your $R$ isn't an equivalence relation, @orlp, as you stated it.

If all evens are equivalent and all odds are equivalent, then $\Bbb N/R$ has two elements.

orlp

@TedShifrin no

Leaky Nun

@TedShifrin I think he probably meant the odd-even topology

orlp

21:33

it relates 2 to 3 and vice versa, 4 to 5, etc

Ted Shifrin

Oh, I see.

orlp

and each number to itself, of course

Ted Shifrin

That wasn't exactly clear from your wording.

orlp

@LeakyNun this isn't a rigorous argument, but it's clear to me that the answer is either 0 or 1 because we're comparing cardinalities of infinities here

Ted Shifrin

So, @Alessandro, you're back to threatening people on the streets? :D

Leaky Nun

21:35

@orlp [0,0.5] is uncountable yet anyone would answer 0.5.

Semiclassical

Equivalent w/r/t quotient by 2

Alessandro Codenotti

@TedShifrin Nah, I'm studying analysis now, I have an exam on the 11th

orlp

@LeakyNun why does the domain of $A$ matter?

Ted Shifrin

Ah, more important to kill analysis than to kill fellow humans :)

Leaky Nun

@orlp I'm talking about $S$

Alessandro Codenotti

21:37

unless analysis kills me first :P

Leaky Nun

If $S$ were [0,0.5] you wouldn't be comparing cardinalities and come up with "either 0 or 1" @orlp

orlp

but $S$ isn't $[0, 0.5]$

Semiclassical

I'd make a riff on Killing vectors but uh

I've never actually learned what those mean

Ted Shifrin

we'd send you to the Killing fields, Semiclassic.

Leaky Nun

@orlp I'm just saying you shouldn't be comparing cardinalities

Danu

21:38

rolls Ted's eyes

Ted Shifrin

LOL, @Danu. Isn't it past your bedtime yet?

Danu

11:30 naw

I am sad that there's no nice tennis on :(

Semiclassical

I'd laugh at that, except that what immediately also comes to mind is Cambodia

Ted Shifrin

Oh, yeah, still early.

We've been through that a month ago, Semiclassic.

Semiclassical

I'm pursuing a new sleep strategy

Alessandro Codenotti

21:40

is that strategy simply "not sleeping"?

orlp

@LeakyNun say we pick some number $x \in [0, 1]$

Semiclassical

Namely, leave my laptops ac adapter at the office so I can't stay up all night on it

Danu

^smart

I do this too sometimes

Alessandro Codenotti

that's genius

orlp

then the equivalence class of $x$ is dense in $[0, 1]$

Ted Shifrin

21:41

Such genius doesn't work for desktops.

Danu

Except now I have two adapters, one of which is always at home.

Foiled again!

orlp

and the chance that we picked the right number in a dense set is $0$

@LeakyNun so my answer would be $0$

Semiclassical

Well, so did i...until I accidentally lost one

Not proud of that

Alessandro Codenotti

actually I'm kind of doing the same, my laptop is at 17% battery now and I think I'll just go to sleep rather than finding the charger when it dies

Ted Shifrin

@orlp: Suppose I ask you to pick a random real number between $0$ and $1$. What's the probability that it's irrational?

orlp

21:42

@TedShifrin 1

Ted Shifrin

So it's not about picking a number in a dense set?

@Alessandro: Then it's dead for you tomorrow?

orlp

@TedShifrin that's different

Ted Shifrin

LOL.

You'd better be able to explain how/why.

Semiclassical

Doesn't prevent me from staying up on my phone, but it's a start

orlp

you're asking what the probability is that we pick a dense subset from another dense set

Jasper

21:42

Hi, LOL.

Ted Shifrin

Hi, Jasper.

Alessandro Codenotti

@TedShifrin I can use it while it charges, we have sockets under every desk in uni

Ted Shifrin

You can kill your phone, too, @Semiclassic.

Semiclassical

Yeah.

Leaky Nun

@TedShifrin he's arguing that the probably of picking $\pi$ from the irrational numbers is 0

Ted Shifrin

21:43

Or you could go to sleep and let it charge while you sleep, @Alessandro :P

orlp

@TedShifrin in my example with $x$ I was talking about the probability of specifically picking $x$ (one number) in a dense set

Leaky Nun

($S$ doesn't have to be dense in $A$, @Ted)

@orlp but $S$ is uncountable

Semiclassical

I should probably charge my phone during the day

Ted Shifrin

I'm aware of that, @Leaky :P

orlp

@LeakyNun but is my analysis incorrect?

under the assumption that we pick a particular $x$ first, the probability is $0$

although that could definitely still be wrong

Semiclassical

21:44

And resist using my rechargeable battery during the evening

Leaky Nun

@orlp let $x \in [0,1]$. The probability of picking $x$ from $[0,1]$ is $0$. Therefore, the probability of picking any number at all is $0$.

orlp

since over all $x$ zeroes can add up to something more :)

Ted Shifrin

Well, adding uncountably many numbers isn't usually a well-defined thing, @orlp.

Alessandro Codenotti

@TedShifrin That would be the most sensible choice

Ted Shifrin

Yes, but I've come to realize you're not always sensible. :P

Semiclassical

21:46

Better to be wise than clever, but both are better than being foolish

Daminark

gives Alessandro a lesson in sensibility

Danu

I'm out

Semiclassical

Oh, Ted. My bureaucracy headaches evaporated last Friday

Alessandro Codenotti

You're not going to give anyone (ok, maybe Balarka) a lesson on sleeping schedules @Dami :P

Ted Shifrin

Night, @Danu.

Good, @Semiclassic.

Daminark

21:47

Ever since coming back to Texas I've consistently slept before 2:30

orlp

no, this argument is fruitless

Ted Shifrin

Otherwise your parents would kill you?

Semiclassical

A director in the student services department evidently intervened so that I could get tuition worked out before the weekend

Have to remember to write them a thank you note

Ted Shifrin

That would be really a nice thing, @Semiclassic.

Semiclassical

Yeah.

It was a huge relief

orlp

21:49

@LeakyNun I don't think I have the tools to answer this question

Semiclassical

That was headache number one gone

Leaky Nun

@TedShifrin what would be your answer?

18 mins ago, by Alessandro Codenotti

@TedShifrin That's not my problem here, but I don't think there's a reasonable probability space for which this set is an event

This would be my answer lol

Semiclassical

Headache number two went away when I talked to the front office again about the TA issue. They'd already given some options, and when I went back to confer with them about it they realized they actually needed a TA with the right load in a certain slot

Ted Shifrin

I guess I haven't convinced myself there's no nontrivial measure on $\Bbb R/\Bbb Q$.

orlp

interestingly I'm not sure if you can make a one to one mapping from $A$ to $S$

my intuition says yes

Semiclassical

21:51

Namely, for the class I'd been gunning for in the first place :)

orlp

but I can't think of a concrete one atm

Leaky Nun

@orlp it requires choice.

Ted Shifrin

Oh, so you can totally stop your bitchin' now, Semiclassic, and get back to "work."

Leaky Nun

it is consistent with ZF that $S$ has more elements than $A$ @orlp

Semiclassical

yep

Leaky Nun

21:52

in the sense that there is no surjective mapping from $A$ to $S$

orlp

$S$ has more??

Leaky Nun

@orlp yes.

Semiclassical

No excuse now, gulp

Ted Shifrin

What was $A$?

orlp

how can you partition a set into one that has more elements?

Leaky Nun

21:53

@TedShifrin $A=[0,1]$, $S=A/\sim$, $x \sim y \iff x-y \in \Bbb Q$

orlp

that seems to violate the very definition of partitioning

Ted Shifrin

I'm with orlp. How can you say the cardinality of $S$ exceeds the cardinality of $A$ when, using choice, you can make $S$ a subset of $A$?

SteamyRoot

Also, just to be pedantic: a set of representatives is not the same as the quotient set

Leaky Nun

oops!

right, it only works if you don't choose the representatives and just consider the number of cosets.

Ted Shifrin

No, I still don't understand.

Leaky Nun

21:55

$A/\sim$ as a quotient (set of cosets) can have more elements than $A$

Ted Shifrin

There's a one-to-one correspondence between the set of representatives (once you've picked it) and the quotient.

Leaky Nun

You don't choose the representatives.

Ted Shifrin

I said to choose them, using choice.

Leaky Nun

Then of course $S$ cannot have more elements if you assume choice.

Ted Shifrin

I hate set theory with a passion, but how can the set of equivalence classes exceed the original set in cardinality?

Akiva Weinberger

21:56

I can believe they could be noncomparable. More, I don't believe.

Semiclassical

"Choose choice."

Ted Shifrin

Well, of course I'm assuming choice.

orlp

@LeakyNun as a set of cosets isn't $|S| = |\mathbb{R} \times \mathbb{Q}|$?

Ted Shifrin

I will not talk to anyone in this room who quibbles with me about choice.

Akiva Weinberger

@Semiclassical But can we choose choice infinitely many times?

Leaky Nun

21:58

@orlp what?

Wildcard

@TedShifrin Is that really a choice you can make?

:P

Semiclassical

well, that's certainly your choice

Ted Shifrin

I've made it.

orlp

@LeakyNun what part is unclear?

Daminark

I'm with Ted on this one, not assuming choice is the wrong life choice

Leaky Nun

21:58

@orlp the $=$.

Ted Shifrin

gives Demonark another month of detention

orlp

@LeakyNun I'm taking the cardinality of both sides

Ted Shifrin

Maybe I can ask Demonark's parents to help me out.

Leaky Nun

{{1,2},{3,4}} has 2 elements, @orlp

Semiclassical

[insert obligatory joke re choice/WOP/Zorn here]

Transcript for

$Mathematics$ Mathematics