The Nineteenth Byte

10:01 PM

okay, let's call f^-1 g f = h

@MartinBüttner Is there a clear way of showing that g can't be the identity function? Oh yes - then the whole thing would be the identity, so can't describe all bijective functions.

Martin Büttner

assume h has a 2-cycle, i.e. h(x) = y, h(y) = x for some x != y

I think this shows that g also needs a 2-cycle to compose this h:

f(x) = n
g(f(x)) = g(n)
f^-1(g(n)) = y   (so that h(x) = y)

f(y) = g(n)
g(f(y)) = g(g(n))
we need f^-1(g(g(n)) == x, but since f (and hence f^-1) is bijective, this requires g(g(n)) == n

does that make sense?

trichoplax

I can see how you could extend that to longer cycles since g can't be guaranteed not to have them, but what about an g that is all 2 cycles?

Martin Büttner

each 2-cycle would have to map to a different 2-cycle in g

trichoplax

Sorry - got my hs and gs mixed up there

Martin Büttner

10:04 PM

hence g would need an infinite amount of cycles of every length for arbitrary h

oh okay

I don't think that helps in computing an h with a 3-cycle

trichoplax

I think I still have them mixed up

We want to define which gs allow for any bijective h?

Martin Büttner

ideally we want to find a single g (or if that's impossible class of gs) which allows us to compose any h, yes

trichoplax

So since an h could have an infinite number of 2 cycles, does your previous argument also demand that g have an infinite number of 2 cycles too?

Martin Büttner

yes

trichoplax

I read back - you said this stronger statement initially...

aditsu

10:09 PM

@El'endiaStarman yes, eval('[0]*b,'*b)

Martin Büttner

I'm not sure how to tell whether such a g exists, I'd probably have to ask math.SE for that.

flawr

Anyone know where would be a good place to ask how to speed up some code?

Martin Büttner

CR?

@Quill ^?

flawr

This code here in particular: github.com/flawr/plane-projective-curve-viewer/blob/master/…

Martin Büttner

Hm, I think this wouldn't even help if g had that form. I think h is bound to have the exact same cycle structure as g due to the bijectivity of everything. So what you'd really need is a class of g that can exhibit any set of cycles.

trichoplax

10:14 PM

f^-1 g f f^-1 g f(x) = x means f^-1 g g f(x) = x

Martin Büttner

I think you're assuming that g is self-inverse

unless I misunderstand what you're trying to say

oh

I do

trichoplax

@MartinBüttner I'm working up to having something to say...

Martin Büttner

haha okay

trichoplax

Just writing half-observations in the hope something will click

Martin Büttner

actually that's a much neater way to prove what I tried to prove above :)

flawr

10:16 PM

@MartinBüttner Looks like some normal subgroups.

trichoplax

I just thought if applying it once leaves x the same you can apply it a few more times - but I overestimated how many more times it would need applying...

Martin Büttner

same works for arbitrary cycles: h^n(x) = x --> (f^-1 g f)^n (x) = x --> f^-1 g^n f(x) = x --> g^n(y) = y

for some y

trichoplax

Ah yes

That's quite neat

If the domain were finite I think this would prove there is no g possible

Martin Büttner

@flawr I don't think I'm looking for actual invariance. I don't want f^-1 g f = g, but I want to find a g (or class of g) such that I can compose an arbitrary h = f^-1 g f from some f.

@trichoplax infinities are weird, but I think it still proves that due to the bijectivity

trichoplax

If the domain is {0}, there is only one possible bijective function, and it works as g

Martin Büttner

10:22 PM

unfortunately, that domain is rather uninteresting in terms of computability ;)

trichoplax

If the domain is {0, 1}, there are only two possible bijective functions, and neither of them work as g. I think {0} is the only finite domain on which a g exists

I'm still no nearer to tackling infinity though...

Martin Büttner

I think if g has an n-cycle you can't compose an h that doesn't have that n-cycle

because f has to map some values into g's cycle, and those values will form a cycle of the same length in h

trichoplax

So even for the infinite case, g has to have an n-cycle, and having an n-cycle precludes it working for all h?

Martin Büttner

yes

trichoplax

That seems watertight

Martin Büttner

10:26 PM

I think the same argument applies to degeneracies if we look at g and h that aren't injective

trichoplax

Does this mean we won't see the challenge/language/other thing you were working on?

flawr

@MartinBüttner On what set should those functiosn work on?

orlp

hello

what are you guys talking about

Martin Büttner

@flawr for now I'm looking at bijective functions on the integers

trichoplax

hello!

Martin Büttner

10:27 PM

@orlp it starts at chat.stackexchange.com/transcript/message/29814746#29814746

@trichoplax well, I guess at least means I'll have to give this some more thought

(on the other hand, the problem I've mentioned here was a slight simplification... the framework I'm actually working with is a bit more flexible, but I don't quite know yet how to formulate that in terms of maths that can be tackled by the same methods as the discussion above)

trichoplax

@MartinBüttner Interesting to see it gradually come into focus anyway - it looked opaque to start with

flawr

@MartinBüttner I do not see the problem, as long as f is bijective you can always find a g?

Martin Büttner

ideally, that I only want a single fixed g, such that for every h I can find an f

trichoplax

@flawr needs to be a single g that works for all h

ninjad :)

orlp

@MartinBüttner I think what you're looking at is homomorphic encryption

flawr

10:30 PM

@MartinBüttner Oh now I see, what restrictions do you have on h?

Martin Büttner

@flawr any computable bijective function

orlp

I'm pretty sure actually

Martin Büttner

@orlp looking it up...

flawr

@MartinBüttner What is computable in this context?

Martin Büttner

computable by a Turing machine (or equivalent computational model)

orlp

10:32 PM

if f is some encryption function (which is invertible through f^-1), and g is some operation, then the study of homomorphic encryption is about finding g' such that f^-1 g' f = g

Martin Büttner

@orlp oh that's pretty close

orlp

the use case

is that you can encrypt data

Helka Homba

strawpoll.me/10275186

orlp

send it off to some cloud

the cloud does operations on the encrypted data without knowing its contents

sends it back to you

Martin Büttner

the main difference is that I'm looking at a fixed g' and can choose f freely to find different g (using your notation)

orlp

10:33 PM

and you can decrypt it

trichoplax

So you can outsource your work without having to trust the worker?

orlp

yes

Martin Büttner

that's pretty cool

trichoplax

So this sounds almost like the inverse problem

Helka Homba

^^^^^^^^^^ Just wondering if blue ray collections are actually common

flawr

10:34 PM

@MartinBüttner How about looking at the class of bijections on the integers that are the identity almost everywhere?

orlp

I mean the most trivial is f(x) = x

for that any g' is g

trichoplax

@HelkaHomba No "none of the above"?

Martin Büttner

@flawr I think you couldn't compose h(x) = x XOR 1 with those

Helka Homba

Do we have an official multi-caret notation? Like ^[10]?

Martin Büttner

(which has an infinite number of 2-cycles)

orlp

10:36 PM

@MartinBüttner actually, the solution to your problem is fairly simple

Martin Büttner

@HelkaHomba it starts with a : followed by the message ID

orlp

given a g' and choosing f arbitrarily, you can construct exactly those g that are permutations of input/output pairs of g'

Helka Homba

@trichoplax Didn't you have no music either? How do you exist o_o :P

Martin Büttner

@orlp yeah, I guess that's sort of what we proved above

which means this approach is rather limited

orlp

@MartinBüttner what open questions do you have?

trichoplax

10:37 PM

@HelkaHomba :P I used to have lots of books. Now I just have Wikipedia and SE

flawr

@MartinBüttner It looks like this is not the identity almost everywhere.

orlp

that I could help with

Martin Büttner

@orlp I'm still thinking about how to formulate it in similar terms to the above problem...

@flawr exactly

Helka Homba

@MartinBüttner Ok :p but responding to oneself is cumbersome :(

orlp

@MartinBüttner if I understand you correctly, you have a question but don't know how to phrase it?

trichoplax

10:38 PM

@HelkaHomba I was thinking this recently. I think someone needs to raise it as a bug

Martin Büttner

@orlp uh yes. more precisely: I had a question, that has been solved (negatively) now, but I think there's more to my underlying problem which I don't know how to phrase yet.

orlp

ok

flawr

I have trouble understanding what is considered a computable bijection on the integers.

trichoplax

@orlp We should propose a new SE site for that. I'd have loads of questions for it

flawr

Is there an incomputable bijection on the integers?

Martin Büttner

10:42 PM

@flawr I think I can construct one if I really want to

let x be a Goedel number. f(2x) = 2x, f(2x+1) = 2x+1 if program x halts. f(2x) = 2x+1, f(2x+1) = 2x if x doesn't halt.

it's clearly bijective, but since you can't compute the condition in the definition, the function shouldn't be computable either.

orlp

not computable everywhere

Martin Büttner

true

I'm sure I could similarly construct something that's computable nowhere though

orlp

well sure

hrm

actually

ignore bijections for now

what is a regular function that's computable nowhere?

actually

I guess the recent result of f(x) = BB(somebignumber) does it for the somebignumber they found

Helka Homba

@Doorknob how do you feel about sliding doors that require no knobs? Friends? Enemies?

Martin Büttner

@orlp yeah something like that

orlp

10:45 PM

who wants to compute BB(BB(42)) for me?

Martin Büttner

brb

orlp

and he was never seen again.....

Martin Büttner

orlp

@wizzwizz4 1 is not a random number

everyone knows that

Martin Büttner

well, I'll go get some sleep and let you know tomorrow if I've come up with a way to phrase the remaining problem in terms of reasonably clean maths ;)

Quill

10:48 PM

@MartinBüttner Performance questions are on-topic, yeah, but reviewers try to review all aspects of the code, so don't get mad if they don't really touch the performance issues

Martin Büttner

cc @flawr ^

orlp

@MartinBüttner but do check out homomorphic encryption :)

Martin Büttner

yeah thanks for that pointer, it definitely sounds interesting (still have the tab open)

trichoplax

@MartinBüttner In the absence of maths, a diagram will do...

Quill

is it zyabin who does the "Unipants Golfing Language"?

Mars Ultor

10:49 PM

@orlp I wonder how much memory it would take up

@Quill Yes

orlp

@MarsUltor pretty sure that also is incomputable :P

Quill

@zyabin101 ^

Mars Ultor

@orlp I know, they already proved BB(5k) or something is ucomputable

@Quill Oh nice

flawr

@Quill What if you explicitly request to review the performance but nothing else?

Nathan Merrill

challenge idea: given an image, and an RBG value, find coordinates of a pixel that has the value in the image

with reading as few pixels as possible

Quill

10:52 PM

@flawr you can't really say "nothing but performance" because that's not how we work... you can just ignore those sections though

it took me a little longer than i thought to extract the inline JS out of the HTML <_<

trichoplax

@NathanMerrill What qualities will the image have?

Mars Ultor

@Quill wat why

Quill

@MarsUltor because inline JS is evil

Nathan Merrill

@trichoplax well, they won't be abstract (like a bunch of black/white lines)

Quill

@MarsUltor and event listeners work differently to onwhatever events, so the property names for values and stuff become slightly different

Martin Büttner

10:53 PM

@orlp @trichoplax one question that might help me with my remaining problem: can you enumerate all bijective functions (on the integers) up to permutation of inputs/outputs. that is can you find a countably infinite set G such that f^-1 g f = h with g in G and arbitrary bijective f can give you any bijective h

Nathan Merrill

meaning that if you find a similar color, you could try to search the local area

Martin Büttner

(probably not gonna reply to any responses tonight though)

Mars Ultor

@Quill I mean why did it take so long

Quill

@MarsUltor because it was 3am in the morning and I had no internet

Mars Ultor

@Quill Eample?

@Quill Why were you working on it at 3am?

Quill

10:55 PM

there was a bit of difference in changing the textareas to divs, but not much, I just gotta finish off this copy code and then I'm good for a PR

trichoplax

@MartinBüttner I'm pretty sure I won't come up with anything before you're next awake...

orlp

@MartinBüttner you can not

let's say I have some permutation of the integers P

I will look at the ordered set (n % 10 for n in P)

this is a set of arbitrary digits

trichoplax

@NathanMerrill So the test images won't be completely smooth but they'll have a tendency towards being so?

orlp

you can reorder the integers mod 10 in any such way that P forms an arbitrary real number

Nathan Merrill

yeah. I was hoping to just find a bunch of random landscape images

orlp

10:58 PM

if you can enumerate all permutations you can enumerate all real numbers, which we know is impossible

trichoplax

@NathanMerrill Will it be guaranteed that such a pixel exists?

Nathan Merrill

yes

trichoplax

Sounds interesting

orlp

actually

hrm, I'm not certain whether that'd still be a permutation

trichoplax

@NathanMerrill I guess you could either go with defining what properties the images will have, or just have a set of test cases and let solutions tailor to those.

Nathan Merrill

11:00 PM

yeah, I think I'll go with test cases

its really hard to define properties of images, unless its generated images

Martin Büttner

@orlp if I understand you correctly this just shows that you can't enumerate all bijective functions. But I just need a subset of them. (Although I think I can come up with a similar argument for that subset.)

Nathan Merrill

and then I might as well make it a mathematical problem

trichoplax

yeah - test cases is more likely to allow discovery of unexpected shortcuts too

orlp

@MartinBüttner you don't need just a subset

@MartinBüttner " can you enumerate all bijective functions (on the integers) up to permutation of inputs/outputs"

I believe you think that the latter part of that sentence defines a subset

it does not, the permutations is exactly the bijective functions

Martin Büttner

I think my wording was probably unclear

orlp

11:02 PM

1

Q: The set of all bijections from N to N is infinite, but not countable

Let $$N=\{0,1,2,3,...\}$$ be the set of all non-negative integers and $A$ the set of all bijections from $N$ to itself. Prove that $i)$ $A$ is an infinite set. $ii)$ There exist no bijection from $N$ to $A$

elementary-set-theory

Martin Büttner

If I have of function g that has a single 2-cycle and is the identity everywhere else, then that allows me to compute all h that have a single 2-cycle and are the identity everywhere else, so I don't need to count those because this degree of freedom is represented by the permutation f

That's what I mean by "up to permutations of input/output"

orlp

121

A: Is symmetric group on natural numbers countable?

Here's a very silly argument to show $|S_\mathbb{N}| \geq 2^\mathbb{N}$. A fact from calculus tells us that a non-absolutely convergent series whose terms converge to zero can be reordered to take the value of any real. So, for each real $\alpha$, there is a permutation such that $$ \sum\frac{(...

@MartinBüttner this is a similar argument to what I did :P

@MartinBüttner I don't know what you mean by this, but I won't bother you any more today, good night :)

Martin Büttner

But I think you can argue that there's a subset of the g which has at most one cycle of any length and then there's a bijection to the real numbers via their binary expansion

Anyway thanks for the help :)

(I should really sleep, but I just noticed that this is where computability comes in. There's only a countable number of h, so I don't need an uncountably infinite number of g.)

orlp

11:54 PM

@QPaysTaxes it's a precondition/postcondition for stack based languages

quartata

Does anyone here have any experience with Pulseaudio?

Transcript for