elementary-number-theory

[runic token]

wait mero do u wanna graph this rq?

i feel like maybe it could help

[torn escarp]

yeah for sure

let me see if it's done geting to 10k

8 9697
8 6529
8 3643
7 71
7 661
7 6359
7 6043
7 5503
7 4241
7 3541
7 3163
7 2267
6 9437
6 8863
6 5791
6 5051
6 4663
6 4591
6 4259
6 401

[errant otter]

imagine some new NT theorem comes out of this

[runic token]

be really funny!

most likely won't happen

but it would be really funny

[torn escarp]

idk how we want to graph this

[runic token]

uhh

just do

p(n) --> n

[errant otter]

"just do desmos"

[runic token]

oh you mean how we'll get this into a graphic software

[errant otter]

yeah

[torn escarp]

https://www.desmos.com/calculator/rrxuw9fphv

lol I think there's probably a better way to paste it into desmos so it's all in one thing

[runic token]

LMAO

i was hoping for a line 😭

a nice line

[runic token]

to look at

but i forgot

scales big

[errant otter]

time to look at probability distributions

😭

[torn escarp]

https://www.desmos.com/calculator/zyrx40bp91

little better for you

[runic token]

ooooh okay that's nice

honestly???

it almost looks

vaguely periodic

[torn escarp]

oh desmos cut out higher data in this version for some reason

too many pts for it in a table I think

[errant otter]

interesting nevertheless

[torn escarp]

https://www.desmos.com/calculator/dlmmwm9sfl

just added another table

could have some periodic stuff to it hmm

[runic token]

wait mero can u get ur program to spit out how many numbers have 7, how many have 5, 4, etc?

[torn escarp]

sure

well I'll just run some stuff on the data as a separate bit of data wrangling, not the program itself

1 467
2 364
3 208
4 116
5 46
6 16
7 9
8 3

or I guess reversed is nicer imo

8 3
7 9
6 16
5 46
4 116
3 208
2 364
1 467

in case you're curious how I'm getting these:

lotta basic unix tools are good for this sort of stuff

[runic token]

ooooooooooh

interesting

[torn escarp]

thousands of points + desmos is conspiring to crash my browser

[errant otter]

XD

[torn escarp]

it's a shame that we dont' have the computing power to get millions of data points

I feel like we can't really see what's happening

just looks like static to me lol

[errant otter]

2 2
1 3
1 5
2 7
2 11
1 13
1 17
2 19
3 23
2 29
1 31
1 37
1 41
2 43
2 47
1 53
4 59
4 61
3 67
7 71
1 73
4 79
4 83
1 89
1 97

Funny, I tried on my own and it seems that there's an error in p = 2

[torn escarp]

you might be double counting with how you set up your loop

1 and p-1 happen to be equal

[errant otter]

right

[torn escarp]

the frequency graph looks more structured

https://www.desmos.com/calculator/8zhcpqzw9h

[runic token]

oh that's nicer

[errant otter]

wow

[runic token]

not very illuminating tho

yet

[errant otter]

distribution curves we go agian

[torn escarp]

interesting

[runic token]

HUH

how did you find that

[torn escarp]

https://www.desmos.com/calculator/siwvqhruja

desmos does it automatically

you take like a table of data with x_1 and y_1 then y_1~ax_1 + b will give the least squares for those pts for instance

[runic token]

we should plug some of those numbers into the inverse symbolic calculator

[torn escarp]

I guess the thing is, we need to normalize this curve somehow

otherwise it'll just keep growing by getting more data points

since the height is the frequency of occurrence

I'm wanting to return to this and thinking from this sort of theoretical starting point we could predict this curve here

but not sure exactly how I'd get started on that lol

[runic token]

i don't know enough group theory to help w that :( sorryyyyy

[torn escarp]

that's ok I'm probably just gonna forget about this problem in a few minutes and move on with my life, it was fun though lol thanks for playing with me here haha @runic token and @errant otter 😛

[runic token]

yes sir 🫡 anytimeeeee

[torn escarp]

on the other hand, it might be an interesting motivator to learn some specific stuff about cyclic groups

[errant otter]

indeed

group theory

lmao idk if my program is doing it right but

when I implemented numpy

I generated 10k in like 3s

lemme check against what u generated

wait it ACTUALLY looks correct

wtf

no way

numpy's that cracked???

[runic token]

probably tbh i heard it's mad efficient

[errant otter]

like bro

I literally interrupted it 5s

and it's alr at 23k

[runic token]

DAMN

yo do the things mero did

cmon graph it

i wanna see

pleaseeeeeeeeeeeeeeeeeeeeee

[errant otter]

Idk how to graph tho

[torn escarp]

oh nice

good work

[errant otter]

I made it do 100k, I wonder what it's at rn

[torn escarp]

nice I just literally printed it with commas and lines then pasted into desmos

[errant otter]

ok tbh I cheated

that's probably why

[torn escarp]

like
1,2
3,4
5,6

[errant otter]

what I did was to download a file of the first 100k primes

so I just accessed each number

[runic token]

LMAO

[errant otter]

and then did the operations

and appended

it's called....

what is it called?

right

[torn escarp]

I think gp has the primes cached up to like 100k or so too

[errant otter]

"manual precomputations"

[torn escarp]

I think running the program backwards or something could optimize it, there's definitely work that could be done I think to make it better

but I think numpy probably did better idk haha

[errant otter]

this is the first 23k I did before I cut it off btw

it's taking quite a bit of time to do 100k as expected

factorials do be like that

oh WAIT

DUDE

WE WERE SO DUMG

WE COULD HAVE SAVED THE PREVIOUSLY COMPUTED FACTORIALS TO OPTIMISE

BROOOOOOOOOOOOOOOOOOOOOOOOOOOOO

💀

[torn escarp]

apparenly by default gp precomputes the first 65,000 primes which is more than I went to, so it's inefficient than what you're doing haha

[torn escarp]

yeah, or used how factorials are computed to do them in ad ifferent order

[errant otter]

mhm

[torn escarp]

like compute n! and then reduce for p < n

[errant otter]

mhm...

[torn escarp]

think that's what you're saying already so I'm late to that party haha

[errant otter]

man how I love computers, rip to 19 century NTheorists

[torn escarp]

lol

ok I guess we still need to graph this then

[runic token]

they woulda had to figure ts out themselves

[torn escarp]

you can probably graph with python or something with some library, I'd have to find one or something I guess

[errant otter]

does desmos accept json

[torn escarp]

but I'll paste in desmos directly

I forget, I think it might

[errant otter]

wait that works?

[torn escarp]

yeah that's what I did earlier

[torn escarp]

put your data like this

[errant otter]

damn

[torn escarp]

well it'll break the table

[errant otter]

shit

I should have inserted commas

[torn escarp]

when I did it like (a,b) then it made separate points

[errant otter]

not spaces

[torn escarp]

just make a new program to go through the file and do it

[runic token]

^^

[torn escarp]

well, I'll just do it cause I already did it earlier

[errant otter]

[torn escarp]

desmos doesn't like it

[runic token]

LMAO

[torn escarp]

ctrl+v and immediately froze

yeah need to get some kind of graphing library or somethin

let's see what we can find

[errant otter]

hm

geogebra

[errant otter]

literally got overloaded

bruh

I can't find a file with factorials in it

[runic token]

i think if someone has mathematica pirated here it would be easy

[errant otter]

istg tho the 1millionth factorial has like
over 550000 digits

💀

no wonder my program is not terminating

I'd bet it's around the 40ks rn

[errant otter]

shhhhhhhhh

Well I do but idk how to use it + it's laggy

[runic token]

wait kmm can u check the highest number so far

i feel like if it's in line w what we've seen

and assuming it grows slower the hgiher it gets

it should be at like

15?

[errant otter]

I can't unless I terminate the program

[runic token]

can u check how far in it is?

[errant otter]

nope I didn't add that feature else it'll impede on computation speeds

wel tbh

I might as well abort

and improve my code

hm....

it hit 566k

impressive

[runic token]

oooooooooooooooh

that's damn good we take it

[errant otter]

highest in that range is 9

[runic token]

wait

i see a nien!

nine!

niceeee

[errant otter]

boom

geez 455kb

[runic token]

💀

what's the biggest number so far

[errant otter]

from a glance

nothing seems to exceed 10

this is suspicious

[torn escarp]

weird yeah

[errant otter]

very sus

[torn escarp]

grows very slowly

[errant otter]

wonder if that'll be broken

if we went higher

time to optimise code

here we go

"no file for factorials? Fine, I'll make it myself"

oh wait

I used wrong command

LMFAO

wholly FUCK

it's 211MB

💀

not stonks at all

[runic token]

💀

kmm what did u do 😭

[errant otter]

I tried making a file with factorials

it went balooney

thank god my PC's pretty strong

[errant otter]

eyo?

there was one that exceeded 10

wtf

[torn escarp]

generating an american flag I guess

[errant otter]

LMfAOOOOOOOOOOOOOOOOOOOOOO

hidden truths: the math behind the american flag

[runic token]

huhhhh

we skipped a number

[torn escarp]

11 1
9 10
8 48
7 149
6 385
5 1085
4 2450
3 4845
2 7547
1 9151

computing frequencies from the data

which is 11 though? heh let's find out

[runic token]

8 3
7 9
6 16
5 46
4 116
3 208
2 364
1 467

this is the original one

hmmmm the frequencies actually look like

relatively similar

right?

like

[torn escarp]

yeah actually let me graph it too

[runic token]

similar to a surprising degree

[errant otter]

well if u wanna compute freqnency

[torn escarp]

awk '$1==11' random.txt
11 292627

[errant otter]

just use a dictionary

tho sadly it'll result in us losing the data of which numbers had this corresponding number

[torn escarp]

I already computed it from the data

just sort by the number of occurrences and throw away the other number and then count them up

that's really all I'm doing here cat random.txt | awk '{print $1}' | sort | uniq -c | sort -n | awk '{ print $2, $1}'

awk '{print $1}' grabs just the first entry, then I sort it, then count up the unique entries and count them with uniq -c then the rest is me just reorganizing it to look cute

(idk if you care about this just figured it might be nice to explain tho)

[runic token]

oooooooooooooh

no i care that's neat

[errant otter]

noice noice

ye that's kewl

[torn escarp]

https://www.desmos.com/calculator/wyywxl7xhl

[errant otter]

cat random.txt

nice

[torn escarp]

haha that's not entirely necessary it's just to keep the random.txt at the beginning of the pipeline

[errant otter]

now to work out the std. deviation and all those stats stuff

[torn escarp]

as it's written, I actually put k where 1/sigma^2 is

so if I just rewrite it in terms of that it'll tell us directly

[errant otter]

noice

[torn escarp]

https://www.desmos.com/calculator/b1xsf7jpqz

m and s are the mean and std

well actually I added a +C to it to raise it up

so maybe I should remove that

[runic token]

do you think if we scale the bottom graph appropriately we'll get a really good approximation of the top graph

[errant otter]

hmm geez, I need to learn my statistics

[torn escarp]

actually

I've messed up the parameters a bit let me fix them now

[errant otter]

cmon python you can do ittttttttttttttttttttttttt generating the first 100k factorials

[torn escarp]

doesn't look super promising

[errant otter]

oof

[torn escarp]

I ust divided the y value by the first element

[errant otter]

maybe this is da wrong approach

[torn escarp]

lol oh definitely

we just pulled a gaussian out of our butts

could easily be something else

[errant otter]

hmmmmmmmmmmmmmmmmmm

[runic token]

tbh im willing to assume it's a gaussian js bc that looks pretty enough

[torn escarp]

like if we think of the probability of what curve we'd expect of pulling without replacement idk

I'd have to look up stuff and think about it to know what that would be

[errant otter]

peak maths: "It looks like a gaussian, so assume it is a gaussian"

[errant otter]

primes berrt

[torn escarp]

actually just shows the first line but this is the plotting program

[errant otter]

geez it's taking forEVER to generate the first 100k factorials

[torn escarp]

I just did the hacky thing, probably there's a way to read the file in python to get it but I just said screw it and threw the data in a list

[errant otter]

based mero

[torn escarp]

matplotlib was what I found an example for

[torn escarp]

referring to this earlier

[errant otter]

naruhodo

[torn escarp]

an alternate way to look at the data

cat random.txt | awk '$1>hs {hs=$1; print $1, $2}'
1 2
2 7
3 23
4 59
7 71
8 3643
9 62939

[errant otter]

[runic token]

LMAO

[errant otter]

latex moment

[torn escarp]

lol

weird seems like my program's wrong

where's 11

[runic token]

did it go high enough

[torn escarp]

oh I just forgot to copy the last line

lol

cat random.txt | awk '$1>hs {hs=$1; print $1, $2}'
1 2
2 7
3 23
4 59
7 71
8 3643
9 62939
11 292627

[errant otter]

interesting
no 10

[runic token]

why is ten skipped

[errant otter]

avoids 10 like the plague

[runic token]

that's so silly

[torn escarp]

I think 10 happens after 11

I mean

5,6 as well

[runic token]

ohhhh true

[torn escarp]

71 occurs so soon

[errant otter]

sus

[runic token]

out of context this is really funny actually

[torn escarp]

that it's already beat out 5 and 6 from occurring

haha

well we know it occurs cause we saw the frequencies earlier

and all were nonzero

[runic token]

right

[torn escarp]

it is interesting how it skips

[runic token]

gahhh

we need more numbers

[errant otter]

either that or

use your brain

[torn escarp]

actually I should have written the program simpler, then I'll explain it

[runic token]

couldnt be me kmm

[errant otter]

okok assume n! = -1 mod p

can we conclude anything abt (n+1)!

[runic token]

yes

(n+1)! = -(n+1) mod p

[torn escarp]

it looks at the first entry $1 and if it's larger than the current highscore hs (initializes to 0 by default) then it will set the new hs hs=$1 as that entry and then print the line print
awk '$1>hs { hs=$1; print }' random.txt
1 2
2 7
3 23
4 59
7 71
8 3643
9 62939
11 292627

awk has come in surprisingly handy for dealing with this math data, didn't really expect to use it on the weekend here lol

[runic token]

oooh

[errant otter]

hmmge

[runic token]

are these the first numbers that reach the new number

[torn escarp]

yeah

[runic token]

that could be interesting!

maybe those show a pattern

none of them are even

(except two)

[torn escarp]

cat random.txt | awk 'BEGIN{OFS=","}$1>hs { hs=$1; print $1, $2}'
1,2
2,7
3,23
4,59
7,71
8,3643
9,62939
11,292627
paste this into desmos (after I reload it cause it froze again...)
https://www.desmos.com/calculator/wa90okiazc

[errant otter]

LOL

desmos

wait I meant

latex

[torn escarp]

looks like it might be exponential growth

[runic token]

tell me that doesn't look like ae^x

[torn escarp]

eh doesn't look so well https://www.desmos.com/calculator/uqpa8fdavk

[runic token]

ah im sure if we zoom out far enough it checks out

[torn escarp]

if you look at the smaller points they are not too grat either idk, I guess it's debatable

[runic token]

hm

how does one run the line of best fit on this curve

[errant otter]

mfw it approaches e^x

also geez

it hasn't generated the 100k factorials yet

I'm beginning to question if it's even computationally reasonable

[runic token]

i bet it is

if you store the factorials

from before

[errant otter]

ye I did

[runic token]

oh 💀

[torn escarp]

ust curious looking at the differences between consecutive terms:

[errant otter]

what I'm doing is basically this

quite simple

[runic token]

huh

ur right

those are weird numbers

[torn escarp]

71 is honestly the weirdest one

[errant otter]

it's just x = 1, multiply by 1, store value, mult by 2, store, 3....

[errant otter]

fr....

[torn escarp]

although 292627 is pretty weird for skipping 10

so that's cool

[errant otter]

let's see if we can find any patterns when we sum teh digits

[runic token]

maybe it's bc 17 is the largest number which occurs as a prime factor of an order of a sporadic simple group

[torn escarp]

I could imagine some relation to like n! and having subgroups of S_n etc etc doing idk what

but I don't know what a sporadic simple group is

tbh in a year from now I think the main thing I'll remember is that (p-1)! = -1 mod p doesn't mean p-1 is the minimal number that makes n! = -1 mod p true lol

surely we can prove this is true for infinitely many cases

it seems pretty common to occur

or at the very least we can prove the probability if we assume it's random follows somethin

[errant otter]

sus stuff

[runic token]

it not only seems random but it seems that more and more numbers do not have p-1 as the minimal number to that being true

as we go up to infinity

[torn escarp]

like ok if I rephrase it slightly in terms of being random and group theory, think of it this way:

start with {0,1,2,...,2n-1} and then pick a number at random without replacement

call your number x, then keep taking numbers out and adding to your x and reducing mod 2n

how often would you expect to have x=n before you run out of numbers to draw from the pile?

[runic token]

isnt this more combinatorics

[torn escarp]

it's whatever you want it to be

do you see the relation to the original question or should I explain a bit

as long as this question makes sense on its own we can try to work on this new probability question on its own merits though

(I'm trying to shield you from the group theory translation I did, that's all)

with a loosening assumption on how it's random

[errant otter]

literally being like veritasium when trying to explain p-adic numbers

desparately avoiding any mention of AA

[torn escarp]

😩

I didn't watch that p-adic number thing but I was afraid I'd see people talk about that now haha

[runic token]

trust ill tell you if i cant handle it

[torn escarp]

I probably have to watch it just so I can anticipate what people will say about it

[runic token]

it's a very silly funny video

[torn escarp]

so the structure of multiplication mod p is not really very predictable in this sense

like if I give you an element of Z/pZ* (the multiplicative group of integers mod p) and ask you to tell me what order it is in the group (how many times you multiply it by itself to make 1) then it's hard to compute

and that problem is called the discrete logarithm problem and some security depends on no one knowing a great way to solve this problem in certain cases

so we might as well just assume if we just start looking at the numbers in order like 1, 2, 3, 4, 5,... then we'll just assume for the sake of argument that their order is random

this is what we're looking at when we look at n for n!, we're just multiplying these on one after the other and seeing if we make -1 mod p

[runic token]

oh!

[torn escarp]

this multiplicative group happens to be a cyclic group with p-1 elements

[runic token]

ive heard of that

that's how uhhh

wait i remember this

[torn escarp]

so I turned it around to talking about addition mod 2n, here 2n is really p-1

[runic token]

OH

thats how

DHKE

works

[torn escarp]

and n+n=0 mod 2n

just like -1 * -1 = 1 mod p

so that's the isomorphism I'm looking at

basically the logarithm of multiplication mod p

and then assuming those are random when given to us by computing n! (not the same as the n in 2n, bad choice of new variable my bad)

[runic token]

rightttt

bc 2n is just according to p

and the new n is what we're computing!

[torn escarp]

log(n! mod p) = log(1)+log(2)+...+log(n) mod p-1 I suppose might be nice

to sort of think of it like that

log(-1 mod p) = (p-1)/2 mod p-1

[runic token]

wait i'm confused

isn't this noninteger

[torn escarp]

or I would rather throw away the mods and just have it understood what the domain and range types ar

this "log" is a map from Z/pZ* to Z/(p-1)Z

I think they usually use like ind(x) or ord(x) instead of log(x) for this

and I probably should specify a little more like a base of the logarithm, like some generator

so like let's pick p=5

g=2 or g=3 which would you prefer

I'll do g=2 you do g=3 afterwards

[runic token]

sure!

[torn escarp]

mod 5 is understood:
2^1 = 2
2^2 = 4
2^3 = 3
2^4 = 1

now we can map them to what order they are err

actually I might be saying that wrong earlier, I think maybe just ind, not ord

order is something else

order is what power you need to make the identity

ind is the index, which I believe is usually used for "log"

[runic token]

right

[torn escarp]

I'm kinda making a mistake in doing two separate things on accident cause I didn't think ahead just started writing haha

[runic token]

so we would say

ind(2) in this case?

or

ind(whatever) but w base of 2?

[torn escarp]

here I'm saying ind(2)=1, ind(4)=2, ind(3)=3 and ind(1)=4

or really ind(1)=0

although it doesn't matter because remember 2^4=2^0 = 1

ind(x) is well defined mod 4

since the exponents cycle back around

[runic token]

hm

let me think on that for a sec

[torn escarp]

like for instance, $2*3 = 1 \mod 5$ which as exponents looks like $2^1 * 2^3 = 2^{1+3} = 2^4 = 2^0 =1 \mod 5$

[sterile pumice]

Merosity

[runic token]

OH

i love examples

okay okay

[torn escarp]

maybe more clearly,

$$g^a * g^b \mod p = g^{a+b \mod p-1} \mod p$$

[sterile pumice]

Merosity

[errant otter]

damn

[torn escarp]

so we're going from multiplication mod p to addition mod p-1

[errant otter]

wtf it looks so much like FLittleT

[torn escarp]

it is flt haha

except we're just thinking about it as logs instead of exponentials, same idea

[runic token]

ohhhhh

so for three

we would have

uh whats 3^4

[torn escarp]

1

[runic token]

i forget

[torn escarp]

fermat's little theorem

[runic token]

OH

convenient

so we have

3, 4, 2, 1

so

[torn escarp]

yeah, so maybe it'd be clearer if I had been writing like log_2(x) and now you're basically doing log_3(x)

[runic token]

ind(3)=1

ind(4)=2

etc?

[torn escarp]

at least, I see no good reason not to use logarithm notation like I'm doing cause it feels sane to me

yeah exactly

[runic token]

no it makes sense

[torn escarp]

well only 2 more to go

you should just do them haha

[runic token]

ind(2)=3

and ind(1) = 0

or four?

[torn escarp]

0 is best imo

just keep them to {0,1,2,3} for mod 4

you oculd wrap around further like 2^5 = 32

[runic token]

right right

[torn escarp]

so what's ind(32)

[runic token]

5!

or just

1

right?

[torn escarp]

yeah, alternatively since 32=2 mod 5

[errant otter]

naruhodo

[torn escarp]

so you can do it inside or outside

if that makes sense

ind(32) = ind(2) = 1 is how I did it doing mod 5 inside

or ind(32)=ind(2^5)=5 = 1 mod 4 outside

[runic token]

it makes senseeee

[torn escarp]

this is what a group homomorphism allows you to do f(x*y)=f(x)+f(y)

going between multiplication and addition, we could compute it eithe way as the group with multiplication or the group with addition

although we have something stronger, we have a group isomorphism, this is invertible

[errant otter]

nani

[torn escarp]

but just trying to tie it into stuff a bit to help give you examles for learning group theory later

[errant otter]

me with my self-insert nanis be like

[torn escarp]

lol

[runic token]

what does invertible mean here

[torn escarp]

we can go back and forth

without losing information

so like lt's say I give you the set {1, -1}

and witht he operation multiplication that gives us a group

a group is a set with a binary operation that obeys some rules

so now we can make this homomorphism: f(x)=x^2

and see that it satisfies f(xy)=f(x)f(y) for all x,y in {1, -1}

but we can't invert it cause both 1 and -1 map to 1

[errant otter]

so would that require bijectivity?

[torn escarp]

yep

[errant otter]

alrighty

so I haven't lost my brains entirely yet

[runic token]

ohhh okay okay

so what if we had

[torn escarp]

the reason it's nice to have an isomorphism is that basically means we're just relabelling the symbols of the group

we're not "smashing it down" into a smaller group

[runic token]

-1,1,i,-i

[errant otter]

isomorhpism theorems be like

[runic token]

under x^2

hm

wait

no

nvm

dang

[torn escarp]

another isomorphism we can make is think of multiplication with {1, -1} and addition mod 2 with {0, 1}

these are really just a relabelling of the symbols we use

[runic token]

hm

[errant otter]

naruhodo

[torn escarp]

-1 * -1 = 1 is really arelabelling of 1+1=0 mod 2

replace -1 with 1, replace * with + and replace 1 with 0

[runic token]

OH

how would you like

formalize that notion

[errant otter]

"I formalise it with the term 'isomorphism'"

[torn escarp]

you basically just rewrite it as x mapping to f(x)

it's important to think of the domain and codomain

f: {1, -1} -> {0, 1}

so while 1 lives in the multiplication world on the left, 1 lives in the addition mod 2 world on the right

f(1)=0 and f(-1) = 1

and f(x*y) = f(x)+f(y)

[runic token]

ohhhhhhh

[torn escarp]

so that's how the elements and binary operator translate over

[runic token]

okay okay nice

[torn escarp]

yup

[runic token]

is that the proper notation?

[torn escarp]

I would probably be more terse in practice

like f: G->H

[errant otter]

notation brrt

[torn escarp]

but in our case G is still that same data of a set with binary operatior

and same for H

G = ({1, -1}, *) and H = ({0,1}, + mod 2) you could write something like this

although there are bunch of other notations for things like this

[runic token]

ohhhhhhh

okay okay

[torn escarp]

like when you learn about quotients people often write Z/2Z for addition mod 2 and Z/pZ* for multiplication mod p

[runic token]

and if you had more elements

hm

wait

you can only have an isomorphism if the cardinalities are equal

right?

[torn escarp]

yeah

if there's not even a set isomorphism, you can't have a group isomorphism

it starts to get hairier when you get to larger groups which have the same cardinality, now telling groups apart might require looking at other properties of the elements or operator

[errant otter]

interesting

bery bery interesting

[torn escarp]

lol I feel like we kinda diverted from our original goal but that's fine

I think this is probably more important

but I think that should make it much clearer how basically fermat's little theorem sorta tells you multiplication mod p is the same as addition mod p-1

you're just relabelling some symbols in a sense

[runic token]

that actually does make sense

thank you!

[torn escarp]

yeah you're welcome

also our example showed that relabelling to addition wasn't even unique

it depended on which generator we chose, like when I did 2 and you did 3, we ended up with different looking translations that were still consistent

[runic token]

ohhh that’s true

[torn escarp]

in fact it might be clearer to see this through another isomorphism you're familiar with

when we use the complex numbers {1, -1, i, -i} we could do the complex conjugate

since adding the roots of x^2+1 has this ambiguity of which is i and -i, it doesn't really matter which we pick

similarly we can map 2 to i or 3 to i

[runic token]

hmmm

[torn escarp]

going from multiplication mod 5 to multiplication in the complex numbers

f(2)=i is enough to unravel everything

f(2)^2 = i^2 has to be true

cause f(2*2)=f(2)*f(2) as a homomorphism

[runic token]

right

[errant otter]

[torn escarp]

we have f(4)=f(2)*f(2)

f(4)=i*i

f(4)=-1

[runic token]

oh so it cycles!

[torn escarp]

of course 4 is -1 mod 5 anyways

yeah

[runic token]

that makes sense

[torn escarp]

similarly f(3)=f(2^3)=f(2)^3= i^3 = -i

and so on

but we could have done the reverse to begin with and picked f(3)=i

and gotten f(2)=f(3^3)=f(3)^3 = i^3 = -i

yeah so we just sorta went through a bunch of different isomorphisms but the kind of nice thing is group theory lets us zoom out and not really worry about these details

we're really just relabelling the same group here

whether we saw it as addition mod 4, multiplication mod 5 or multiplication in the complex numbers

it's really the same structure, so it's sort of nice to bounce between perspectives like this

[runic token]

ohhh so we can make thms abt like one group while it might be hard for another group

[torn escarp]

depending on what's convenient to us

[runic token]

but bc of isomorphism

[torn escarp]

yeah exactly

[runic token]

it still applies

[errant otter]

[runic token]

woah

who came up w they

that

[errant otter]

lmao

[runic token]

that’s so smart

[torn escarp]

I dunno haha

[runic token]

big brain

damn

[torn escarp]

I suppose in some sense the first isomorphism we all really kind of get used to seeing is exponentials and logarithms

[runic token]

i wish i was like that fr

[errant otter]

fr

[runic token]

hm

those are groups?

[torn escarp]

yeah, see if you can figure out what the sets and operators are

[errant otter]

Mmmmmmmmmmmmmmmm

[torn escarp]

maybe it helps to pick one, like logarithm

what's the domain and codomain of this

[runic token]

sets are a^x for exponentials and the operator is multiplication?

[errant otter]

set of real numbers- no shit

[torn escarp]

haha not exactly

[errant otter]

naaaaaaaaaaaaaaaani

[torn escarp]

set not quite right, but operator would be multiplication

[runic token]

hmmmm

[errant otter]

MmmmMMMmmm

[torn escarp]

I think once you see it it'll be clearer, but I'll let you struggle together for a bit while I make more tea

it's good for you to figure it outhaha

[errant otter]

ok fair

[torn escarp]

like precisely what is the domain and codomain of log: A -> B

what's A, what's B?

[errant otter]

Oi valley you ask GPT, I'll ask bing AI

[runic token]

LMAO

a is

postive reals

b is all reals

operator is

addition?

[errant otter]

wait

[runic token]

i think?

[errant otter]

why addition

[runic token]

because ln(a) + ln(b) = ln(ab)

[errant otter]

hmge

[torn escarp]

A and B each have a binary operator

remember a group is a set and binary operator

are they both addition then?

[runic token]

hm

no

wait

i feel like it should be no

i think the exponentials should be multiplication

ohhh the domain for exponentials is all real numbers

and the codomain is positive reals

[torn escarp]

the exponential or log is not where the binary operator is

that's just the map between the groups

[runic token]

HUH

oh

[errant otter]

HUH

oh

[runic token]

mf

[errant otter]

[runic token]

so for the all reals to positive reals

then

hm

multiplication

[torn escarp]

just like log maps a number from positive reals to all reals

log maps ??? operator to ??? operator?

log(x+y)=log(x)*log(y)
log(x+y)=log(x)+log(y)
log(x*y)=log(x)+log(y)
log(x*y)=log(x)*log(y)

[runic token]

c!

[torn escarp]

which of those looks right and what's going where

[runic token]

multiplication to addition!

[torn escarp]

so is that * to + or + to *

[errant otter]

multiplicative to additive

[torn escarp]

ok cool

[runic token]

ohh and then exponentials

hm

[torn escarp]

so now write exponentials out this way

show how it does the reverse

f(x+y)=f(x)*f(y)

[runic token]

OH

i was thinking abt it the other way

[errant otter]

we can just use the fact that log is inverse of exp can we?

[runic token]

that was silly of me

yes it goes additive to multipicative

and it's unique in that property, right?

[torn escarp]

yeah

I guess it sounds like I'm asking something intense I really just meant

write it in terms of like f(x)=e^x

I want to see the + and * flopping around

[runic token]

ohhh but the reason group theory is nice is because we can prove something for this and then extend it to different groups

[runic token]

e^(a+b) = e^a * e^b

like that!

[torn escarp]

yeah exactly

that's really all I was looking for, just making sure the basics are clear of what'shappening

just like we relabeled addition mod 4 to multiplication of {1,-1,i,-i} in C

and saw that those are really just the exact same structure

addition of reals is exactly the same structure as multiplication of positive reals

so that's really just all we really have from this particular isomorphism

[runic token]

hmmm

[torn escarp]

this was just to show an example, I don't know if that will feel very profound or anything like that

[runic token]

it's still a nice example though

i think it helped me!

idk abt kmm but it made sense to me

[torn escarp]

that's good

I think we're sorta used to R since kids that it's easy to take it for granted a bit, but the fact that to show that addition of R and multiplication of positive R are the same requires a funny mapping, like log(2) where you're producing irrational numbers often times

for instance, is addition in rationals isomorphic to multiplication of positive rationals?

[errant otter]

mmmmmm

[torn escarp]

if they are or aren't - prove it 😛

also backing up, just like we mapped 2 mod 5 to i or -i

we also didn't have a unique isomorphism here either

f(x)=a^x we had choices for a

anyways just sorta throwing some food for thought at you to play with haha I think that's a good amount for now

we can still keep talking I just won't like keep introducing new stuff haha

[runic token]

i am working on the problem

hmmm

so my initial thoughts were

"oh of course it has to be possible"

[errant otter]

Ummmm okay so I have the sussy feeling like we have to introduce the fact that irrational numbers may pop out to disprove this

[runic token]

so then i thought abt defining some function q to q+

oh

me and kmm are thinking entirely different things 😆

[errant otter]

[runic token]

im sure they're correct tho

bc im having much trouble defining such a function that maps addition to multiplication

[errant otter]

OH WAIT

IAEJGTIupAEUGHAE

\I THINK IG OT IT

so sosososos

ummm

basiucally

[runic token]

we want a function s.t f(x+y)=f(x) * f(y)

oh

but its unique

and clearly it's sometime nonrational

[torn escarp]

it's not necessarily unique

[errant otter]

yeah around those lines? But wait why'd u write f(x)+ oh ok u fixed it

okok

so um

let's say

clearly

[torn escarp]

just like f(x)=2^x and f(x)=3^x are both exponentials (log_2 and log_3 for the inverse)

[runic token]

ohhhhhhhhhhh

true

but it's still unique i thought

not unique

[errant otter]

a number x where f(x) = 2 exists

umm right

[runic token]

but that it always has irrationals

go on kmm

[errant otter]

so since such an x must exist

and assuming that the isomorphism is there

then

f(x) = f(x/2 + x/2)

= f(x/2)^2

[runic token]

hmm

[errant otter]

so

[runic token]

OH

[errant otter]

since f(x) = 2

[runic token]

smartttttttt

vv smart

[errant otter]

basically it'll become sqrt 2 I think?

and that's irrational

but now to prove that there is indeed such an x

[runic token]

well

it just needs to have it so that it doesn't map to perfect squares every single time

oh hold up

nono we dont need to do that

okay so hear me out

if we can have f(x/2 + x/2)

[errant otter]

[runic token]

then why can't we have f(x/3 + x/3 + x/3)

[errant otter]

uh huh

[runic token]

that makes sense to me

and then that means

[errant otter]

lmao that EMOTE

[runic token]

it's gotta be a cube root

and we can just go on

so it would have to be rational

for every single nth root

which is not possible

for any number

[errant otter]

[runic token]

except 0 and 1

but we'll ignore them

[errant otter]

indeed

yessss

my 1st time using the emote

[torn escarp]

you solved it?

[errant otter]

yes

um

I think

[errant otter]

here

umn

I hope

[runic token]

idk

hopefully!

[torn escarp]

haha it sounded like you had a good idea so I think you did

I didn't read it, just was gonna let you rewrite it more cleanly when you're ready haha

[errant otter]

I just abused the guy who got stoned by pythagoras's followers

[errant otter]

alrighty here I go

Suppose that we have an isomorphism between the addition in rationals and the multiplication of positive rationals, denoted by $f: (\mathbb{Q}+) \mapsto (\mathbb{Q}_{>0} \cross$
Since $f$ is bijective, there exists an $x \in \mathbb{Q}$ such that $f(x) = 2$. Since x is rational, so is $\frac{x}{2}$. (I think? Idk how to prove this part tho)
As such, we have that $f(x) = f(\frac{x}{2} + \frac{x}{2})$, and by our assumption, is equal to
$f(\frac{x}{2}) \cdot f(\frac{x}{2}) = f(\frac{x}{2})^2 = 2$, which implies that
$f(\frac{x}{2}) = \pm \sqrt{2}$. But $\sqrt{2}$ is irrational, leading to a contradiction

[sterile pumice]

Kiameimon | Welt Rene (glomed)

[errant otter]

um

done

I thinkl

[torn escarp]

yeah that looks good, I'll help on the parts a bit that need cleaning a little

[errant otter]

I need to learn how to write formal proofs smh

[torn escarp]

since f maps from positive rationals, it's defined on x/2, so f(x/2) is fine

yeah that was plenty formal

if you had tried to do something like f(sqrt(x)) then we'd have problems of course

I probably would have not written sqrt(2) because it's not really an element

like f(x/2)^2 = 2 but since we know f(x/2) is rational we could write it as y maybe for clarity

[errant otter]

ah

[torn escarp]

y^2 = 2 then just say - "nope" cause of the same reason

[errant otter]

[torn escarp]

but nothing too serious really

yeah good work both of you

[errant otter]

[torn escarp]

I think working backwards is sorta tricky like knowing there's an x such that 2=f(x) is a good trick

since this is the number theory channel, this is morally good because we have now officially shown that the rational numbers are more interesting than real numbers

[errant otter]

[torn escarp]

because its multiplicative group and additive groups isn't really just a simple relabeling of symbols like reals 😛

that makes sense though we already knew that, cause rational numbers have prime factorizations while real numbers, there's no barrier to taking roots

[errant otter]

yee

[torn escarp]

if you push your proof a bit more generic and don't fix 2, you could do something like pick an arbitrary rational q, q=f(x) then break it down to q=f(x/n * n) = f(x/n)^n and recognize that f(x/n)=r is some other rational number but in general we can't solve q=r^n for all n

(just to put it more clearly why I said there's no barrier to taking roots)

[errant otter]

yee

that's what valley suggested later on

[torn escarp]

actually groups like this have a name called divisible groups

[errant otter]

cyclic groups
abelian groups
what next?

[torn escarp]

nonabelian groups

lol

have you studied any linear algebra?

[errant otter]

a bit

[torn escarp]

matrix multiplication is noncommutative generally speaking

[errant otter]

mhm

[torn escarp]

so there's a source for some nonabelian groups that might be important to you eventually

[errant otter]

nani

[torn escarp]

also rotations in 3D space

you can take an object like a book on your desk

[errant otter]

uh huh

[torn escarp]

and try rotating it 90 degrees around the x axis or y axis but in opposite orders

and you end up with different ending configurations

[errant otter]

mhm mhm

[torn escarp]

or if you have some dice lying around you can do them both too

anytime in math someone calls something a 'symmetry' they are probably thinking about some specific group moving something around

[errant otter]

sounds like diagonalisation to me

[torn escarp]

somewhat related

the eigenvector matrices you're conjugating by are what make up the symmetries

[errant otter]

[torn escarp]

specifically if we're talking about symmetric matrices, you can think of the symmetries are how those orthogonal matrices reflect or rotate the quadratic forms

like xy=1 is a hyperbola that opens up at a 45 degree angle but then we can rotate it 45 degrees to make (x^2-y^2)/2 = 1 or whatever it is

well we'd have to talk a little bit more about group actions since I'm introducing an extra set here now tha the group is acting on

I think that's enough for tonight lol

[errant otter]

[verbal axle]

does this look right? here p is prime

[torn escarp]

where do you get the upper bound of ceil(sqrt(p))

[verbal axle]

I proved that

[torn escarp]

I'm guessing some kind of tweak on $\sum_{d|p-1}\varphi(d) = p-1$

[sterile pumice]

Merosity

[torn escarp]

but only using d < cbrt(p)

how does that come in

[verbal axle]

yeah that was the part I was not too sure about, I did some playing around and saw that as p gets large, the bound ceil(cbrt(p)) holds, but for some smaller values of p it doesn't

like p = 31, this doesn't hold

ngl I was kinda bluffing, the gap does grow very fast tho

[torn escarp]

I don't think you need to do anything so weird

but idk, nothing pops out to me right away

[verbal axle]

what I could do is use the fact that

my idea is that there is no d that divides p-1 that is greater than sqrt(p)

maybe that plays a role here somewhere

[torn escarp]

hmm the fact that we have the cube root might mean we have to pull out more than that

but it's a start, let's see how that goes for us

[verbal axle]

yeah the cbrt is throwing me off a bit lol

[torn escarp]

already that gets us $\lim_{p \to \infty} \frac{p-1 - \varphi(p-1)}{p-1}$

[sterile pumice]

Merosity

[torn escarp]

so that's 1 - phi(p-1)/(p-1), I don't think $\lim_{p \to \infty} \frac{\varphi(p-1)}{p-1} = 1$ so we gotta be better

[sterile pumice]

Merosity

[verbal axle]

since p is prime $\frac{\varphi(p-1)}{p-1} < 1$ cuz $p-1$ is not prime

[sterile pumice]

ForJoke

[verbal axle]

what if we looked the sum $\sum_{d|p-1, d < \sqrt{p}}\varphi(d)$

[sterile pumice]

ForJoke

[torn escarp]

that's what we just looked at

[verbal axle]

oh wait, wut?

[torn escarp]

oh p not p-1

my bad

I think it's still the same though

here's another way maybe

d | p-1 and d < cbrt(p) we rewrite this condition as d^3 < p and then subtract 1 from both sides d^3 - 1 < p - 1

now factor and we have (d-1)(1+d+d^2) < p-1

we already know d-1 < p-1 not very exciting, but maybe 1+d+d^2 < p-1 if we look at the divisors between these two roots of the quadratic

[verbal axle]

I dont quite see how this helps ngl

[torn escarp]

not sure yet either, but I just finished solving for the roots of it

one is negative, but might as well be 1, the other is positive so

$$\sum_{d|p-1, d<\sqrt[3]{p}} \varphi(d) \le \sum_{d|p-1, d<\frac{-1+\sqrt{4p-7}}{2}} \varphi(d)$$

[sterile pumice]

Merosity

[torn escarp]

at least we know this is true and we have a quadratic now, and then we can mess with that a bit more to simplify it to something more tractable like you had actually -

$$\sum_{d|p-1, d<\sqrt[3]{p}} \varphi(d) \le \sum_{d|p-1, d<\frac{-1+\sqrt{4p-7}}{2}} \varphi(d) \le \sum_{d|p-1, d<\sqrt{p}} \varphi(d) $$

[sterile pumice]

Merosity

[verbal axle]

yeah the far inequalities are easily derived since cbrt(p) < sqrt(p)

[torn escarp]

I guess what I'm saying is, if the sqrt(p) one doesn't work we might be able to tighten it a bit further using this result I just found to make it work if we're nearly close

[verbal axle]

oh that is true

[torn escarp]

although idk where to go from here either so that's why I did that dancing around haha

just figured at least I'll take the paths I could see to their dead ends first

hmmmm

[verbal axle]

the far sqrt(p) doesn't help, I checked this using python, sqrt(p) grows too slowly after a point

[torn escarp]

oh, change it to the lower one I just got too

it probably won't work either if it's too slow growing

so this just needs to be trashed entirely

that's just translating slightly, it's not gonna fix issues in the long term

[verbal axle]

what makes the cube root so special?

[torn escarp]

hmm idk

more playing around, what if we write p=1+dn and d^3 < p and plug it in to make d^3 < 1+dn

this is like a depressed cubic

which is how I feel about it too, not sure if I want to go further down this path

[verbal axle]

yeah no, this gets ugly, fast

I'm sorry but I gotta sleep now, its like 5am where I am💀

I will dream about this question, and hopefully get something fruitful, I will keep you updated

[torn escarp]

same timezone as me lol

sounds good, later lol

[verbal axle]

you should proolly sleep too lmao

[torn escarp]

exactly what I'm doing too

[verbal axle]

gg

[errant otter]

[white lion]

Im trying to understand this proof for 'there are infinitely many primes of the form 4k-1'

[sterile pumice]

jayzsparrow

[white lion]

Interlude 1: how do we know that there must be atleast 1 prime divisor of the form 4k -1?

[torn escarp]

Suppose they're all 4k+1

[white lion]

Ok

btw it is not the complete proof, just up until the part im having toruble with

[torn escarp]

That's fine

[white lion]

wait was that it? 😅

[torn escarp]

Well just giving a hint, you fill in the rest

[white lion]

Suppose all the prime divisors of 4k - 1 is 4k+1?

[torn escarp]

Yeah

[white lion]

suppose there are only finitely many primes of this for $p_1,p_2,. . . , p_n$ and consider the number $m = 4p_1 . . . p_n$ - 1. since m is of the form 4k-1 and m > $p_i$ for all i it follows that m is composite and must have prime factors of the form 4k + 1 or 4k-1. Since the product of any two numbers of the form 4k+1 is again of that form it follows that m has atleast one prime divisor of the form 4k-1

[sterile pumice]

jayzsparrow

[white lion]

ah ok I see what you're saying, gotcha thanks.

[torn escarp]

Cool, you're welcome

[verbal axle]

how many divisors can p-1 have that are less than p^(1/3)

[torn escarp]

was thinking about this

does it help to rewrite it as d <= (p-1)^(1/3)