Mathematics - 2017-01-02 (page 1 of 5)

Balarka Sen

00:59

@AkivaWeinberger The picture you want is $f(x, y) = 0$ except through $y = x^2$ where $f(x, y) = 1/x$

Adeek

hey @arctictern here ?

Balarka Sen

And then make it continuous. I think what you said works; the example I had once upon a long time ago had an $x^5$ in it.

Everything's of the form $x^ay^b/(x^c + y^d)$

arctic tern

@Adeek what's up

Adeek

@artic I am solving the following question. An alternative to the notion of multiset introduced in §2.2 is obtained by
considering sets endowed with equivalence relations; equivalent elements are taken
to be multiple instances of elements ‘of the same kind’. Define a notion of morphism
between such enhanced sets, obtaining a category MSet containing (a ‘copy’ of) Set
as a full subcategory. So, I solved this question before. I also discussed it with you we consider the morphism to be functions that preserve relations.

@arctictern Now I would like to give a description of monorphism in this category and epimorphisms.

@arctictern Are they just injective/surjective relation preserving maps ?

arctic tern

have you seen the proof that inj/surj functions are monos/epis in the usual cat of sets?

Adeek

01:06

Yeah I proved it before.

I think the regular proof for monos will work for this category.

There is a problem I could see for epis.

atleast for the side of a morphism epic then it is surjective.

Balarka Sen

@MikeMiller This is an interesting perspective

Adeek

@artic Remember I showed you the proof as follows: Suppose f is a morphism that is epic, but not surjective. Then, there is a b such that there is no a that mapped to it. Fix arbitrarily $\alpha_1 : B \rightarrow A$, construct $\alpha_2 : B \rightarrow A$ to be same as $\alpha_1$, but different at point b. So this will give us a contradiction.

@arctictern However, in this case we don't know whether this new $\alpha_2$ will be actually a morphism in the our new category Mset.

For the other side we can use the fact that a morphism which is surjective will have a right left inverse so we can use that to show it is epic in this category Mset.

arctic tern

in fact, an epimorphism needn't be surjective here. instead, its range hits every equivalence class in the codomain.

Adeek

oh so it is surjective onto the equivalence class ?

that is something less I see

I guess for monos it would be injective onto equivalence classes right ?

Benjamin R

01:35

@AlessandroCodenotti Thanks. I always think of $| |$ in general terms being particular to vectors, rather than equivalent representation of sqrt, though. But at least my algebra wasn't wrong, it's just a representation thing.

@Fargle I hope one day to achieve enlightenment and become an Algebra, myself. I'll float through the universe.

Adeek

ahaha

Fargle

02:14

@BenjaminR "On all levels except physical, I am a Lie algebra. $[x,[y,z]] = [z, [x,y]] = [y,[z,x]] = 0$"

Balarka Sen

Hi @Fargle

arctic tern

@Fargle apparently a lie algebra L with L' contained in Z(L).

(points at extra equals signs)

Fargle

Howdy @Balarka, @tern

Yeah, I'm tired and know like two total things about Lie stuff.

Balarka Sen

Yeah, shouldn't be $ = 0$.

Fargle

The sum should be.

Balarka Sen

02:26

I need to decide what I want to do today

GFauxPas

@BalarkaSen play video games

Balarka Sen

neat idea

GFauxPas

hth

Semiclassical

Hi chat

Fargle

Hello @Semi

Mike Miller

02:44

wrote a little, played a little, watching stuff now

Balarka Sen

sounds like a nice balance between stuff

Mike Miller

nice balance doesn't get papers written

Semiclassical

The analogy that comes to mind is a classic physics problem.

Suppose I drill a hole through a bead and put it on a circular hoop. If I orient it vertically, then the bead slides to the bottom and stays there.

Balarka Sen

@MikeMiller oh well.

user228700

Hello, everyone :-) I have a quick question about the range of a function. Is it given by [maxima,minima] - {Horizontal asymptotes} ?

Semiclassical

02:52

If I make the hoop rotate on its vertical axis at a slow but constant rate, the bead will stay at the bottom. But if I increase the rate of rotation, eventually the bead will prefer to rise off the bottom and rotate in some circular orbit.

That's the thing: To get things moving fast enough that the equilibrium state is to keep moving rather than fall to the bottom.

DHMO

@Kaumudi.H that is a(n poor) attempt to generalize it

arctic tern

@Kaumudi.H no. the range is the set of outputs the function takes.

Semiclassical

(A forced analogy, perhaps. But oh well.)

user228700

@arctictern Yes, but I am finding methods to determine the range of a given function.

Pissed off layman

@Kaumudi.H what does that notation mean?

user228700

02:54

What notation?

Balarka Sen

That doesn't work in general.

arctic tern

@Kaumudi.H what kinds of functions? a function is just a bunch of ordered pairs. it could be absolute chaos.

user228700

@BalarkaSen Okay..?

Pissed off layman

[maxima,minima] - {Horizontal asymptotes}

arctic tern

@Pissedofflayman [a,b] is an interval, and A-B means "the set of things in A that are not in B"

Balarka Sen

02:55

I mean, look at f(x) = 1 if x = 0 and f(x) = 0 otherwise.

Not all missing values come from asymptotes.

None of them does, in this case.

arctic tern

and horizontal asymptotes can be included in the range

user228700

Wokay, never mind, then. Thanks.

Semiclassical

Here's another way things could go wrong. Suppose I have a function that passes through the origin, rises past $y=1$, and then falls back to $y=1$ and plateaus there.

In that case, $y=1$ is a horizontal asymptote. Nevertheless, $y=1$ is certainly part of the range due to the initial rise.

Sophie

can you construct any regular polygon with a bounded amount of angle primesectors?

Semiclassical

What?

Angle primesectors?

Sophie

03:01

@Semiclassical bisector, trisector, etc

of course you can bisect an angle with ruler and compass

Semiclassical

Do you mean: If you're allowed to do $p$-section on any given angle, are all regular polygons constructible?

With $p$ prime?

Sophie

if you can $p$-sect an angle you can $n$-sect an angle

Fargle

@Semiclassical I think it's asking if there's a finite set of primes that can give all regular polygons.

Semiclassical

Ah.

I'd guess the answer is no, but I really don't know.

Sophie

@Fargle no you can use all primes, only you can only use finitely many steps

Fargle

03:05

Ah. Then my gut says "yes" but I can't really say why.

I'm out of here anyway.

Semiclassical

My feeling is the same as @Fargle.

Balarka Sen

@MikeMiller Say I want to classify framed cobordisms between 1-manifolds in S^3. Bunch of circles are framed cobordant to a single circle by pair of pants; so it boils down to doing so with a circle. A framing on a circle in S^3 is a choice of a "classifying map" S^1 --> SO(2); so it suffices to see that cobordant framing have homotopic classifying maps, right? Then it's $\pi_1SO(2) \cong \Bbb Z$; which is exactly what $\pi_3 S^2$ is.

Mike Miller

yup

Balarka Sen

cool.

Mike Miller

though you should be careful when you see that multiple circle are bordant to one

make sure the framings work the way you think they di

Balarka Sen

03:20

oh whoops maybe I didn't actually pay attention to that

Now it's less obvious to me that pair of pants actually does that when two circles at one end have completely different frames.

Mike Miller

need to check that any framings on two of the circles extend everywhere and determine what the third circle is

Balarka Sen

I am going to ponder on this with the chocolate chip cookies

Pissed off layman

enjoy

:-)

Balarka Sen

03:46

Given framings on two circles one needs a framing on the connected sum. So just make the framing trivial near two small intervals in each circle, delete smaller intervals, and glue. This clearly extends everywhere, except near the nonmanifold section of the pair of pants (where the level set looks like an 8), which is the bit I am worried for

But that's easy to fix, now that I think about it.

Adeek

Hey @BalarkaSen would you like to check my proof ?

Balarka Sen

Depends. What is this proof about?

Adeek

Prove that $\emptyset$ is unique initial object in Set.

Okay ?

Balarka Sen

Sorry, I don't really want to.

Adeek

ok

Jessy Cat

05:30

Algebra whizzes:

0

Q: $H\trianglelefteq G$, $H \cap G^{\prime}$ trivial implies $H$ in center of $G$?

This question is related to this other post: I was wondering if proving that $ H \trianglelefteq G$ and $H\cap G^{\prime} =\{e\}$ (where $G^{\prime}$ denotes the commutator subgroup of $G$) implies that the elements of $H$ commute with the elements of $G^{\prime}$ is the same as proving that $H \...

Make a cat happy

Bacon!

Jessy Cat

06:08

The rest of the civilized world, eh @arctictern

I am completely uncivilized/uncivilised (pretty much frigging savage in all parts of the world).

DHMO

I need a fast integer n-root algorithm

I thought most of the time is spent on producing the product of consecutive numbers

but turns out most of the time is finding the n-root of a large integer

Dair

stackoverflow.com/q/1100090/667648 ?

DHMO

not square root

Dair

oh. yeah. my bad...

DHMO

anyway, I guess I should be using Newton's method instead of binary search

Dair

06:21

what language are you using?

DHMO

python

Dair

gmpy2.readthedocs.io/en/latest/mpz.html I believe iroot is the "integer root"?

you're going to have a hard time beating gmpy given you're writing it in python and gmpy is a Python wrapper around C

DHMO

you're right

static PyObject *
GMPy_MPZ_Function_Iroot(PyObject *self, PyObject *args)
{
    unsigned long n;
    int exact;
    MPZ_Object *root = NULL, *tempx = NULL;
    PyObject *result = NULL;

    if ((PyTuple_GET_SIZE(args) != 2) ||
        ((!IS_INTEGER(PyTuple_GET_ITEM(args, 0))) ||
         (!IS_INTEGER(PyTuple_GET_ITEM(args, 1))))) {

        TYPE_ERROR("iroot() requires 'int','int' arguments");
        return NULL;
    }

    n = c_ulong_From_Integer(PyTuple_GET_ITEM(args, 1));
    if ((n == 0) || ((n == (unsigned long)(-1)) && PyErr_Occurred())) {

Dair

From gmpy?

DHMO

yes

Dair

06:28

is it fast enough?

DHMO

haven't tested lol

I want to use my own algorithm lol

I can't even find the code responsible for the root

Dair

Yeah, it calls mpz_root

DHMO

and I can't find mpz_root anywhere

Dair

That's because it belongs to GNU MP

not gmpy

DHMO

I see

Dair

06:32

plus python uses GMP natively so it doesn't need to include the library anywhere

github.com/SaberMod/gnu-gmp/blob/…

gl.

Dair

06:58

if you have to write your own, have you considered switching python implementations?

DHMO

what is python implementation?

Dair

so a language is just a grammar, then there is a program that runs/compiles the file

the program that runs/compiles the language is the interpreter/compiler

and it is referred to as an implementation of a language

standard python implementation is CPython

but you could also use Cython or PyPy for instance

DHMO

I see

Dair

do you use the integer square root function a lot?

PyPy would probably be the easiest implementation to use for a speed boost.

Sophie

07:14

@DHMO god choose one indent and go on with it

DHMO

@Sophie ?

Sophie

the indentation is inconsistent

DHMO

I see

@Dair Netwon's method is way slower than binary search lol

Dair

Well that sucks...

what problem are you trying to solve?

@Sophie That isn't even DHMO's code lol

Sophie

doesn't make it less inconsistent

DHMO

07:18

@Dair i'm just trying to find the n-th root

Dair

@DHMO Oh I thought you mentioned about it being a bottle neck or something...

DHMO

oh yes

My code is here.

@Dair do you have any faster algorithm?

Sophie

if you have good code for taking logs and exponentials then that might be faster

@DHMO what do you mean binary search?

DHMO

def nroot(x,n):
	lo = 1
	hi = x//n
	while lo <= hi:
		mi = (lo+hi)//2
		test = mi**n
		if test < x:
			lo = mi + 1
		elif test > x:
			hi = mi - 1
		else:
			return mi
	return lo

Sophie

that doesn't look very efficient

DHMO

07:28

how?

Dair

Hey so my internet is acting spotty so if i dont respond you know why

@DHMO I dont understand the problem you are trying to solve.

Sophie

it's naive. I used to compute square roots with that algorithm when I was in school. I'm going to implement Newton's method and compare

DHMO

@Sophie I tried. Newton's method is slower

@Dair I'm trying to find n!=a!b!

Sophie

I think the key is that $x^n-k$ has a root of order $n$ at $k^{1/n}$

why aren't you using the language's built in pow thing?

DHMO

I thought that is float

Sophie

07:31

what?

DHMO

doesn't pow(n,1/3) return float

Dair

It is python, it does return a float, you can round it however.

Sophie

you only need the floor of the thing? That makes it easier

Dair

In theory it would be better to have an integer square root, however the built in pow is written in C

Sophie

Integer square root

In number theory, the integer square root (isqrt) of a positive integer n is the positive integer m which is the greatest integer less than or equal to the square root of n, isqrt ( n ) = ⌊ n ⌋ . {\displaystyle {\mbox{isqrt}}(n)=\lfloor {\sqrt {n}}\rfloor .} For example, isqrt ( 27 ) = 5 {\displaystyle {\mbox{isqrt}}(27)=5} because...

DHMO

07:33

that wouldn't work @Sophie

my numbers are very big

the precisions would be all lost if you just floor it

Sophie

I don't get it

Dair

oh that's a good point too... if the numbers are too big they cant be put into a float.

disregarding the precision issue...

Sophie

floats work with numbers up to like $2^{53}$

Dair

yeah, but he's using a GMP integers

with arbitrary precision

DHMO

@Sophie i'm quite sure that 100! >>> 2^53

Sophie

07:38

do you only need the square root or higher roots too?

DHMO

higher roots also

Sophie

you could use Stirling's approximation (which is convenient to take a log of) divide by n then exponentiate

DHMO

sounds good

nah, too imprecise

Sophie

you just want the floor of the thing. It should work

DHMO

try it

try using your approach to calculate (200!)^(1/4)

exp((200*ln(200)-200)/4)

it's too imprecise

Sophie

07:50

what part of the program is this for?

DHMO

to check if n! is the product of c successive integers

Sophie

Stirling's approximation gets $\frac{\ln(200!)}4$ off by 0.0001 which is indeed not enough to guess which integer $200!^\frac{1}{4}$ floors to

Starfall

you can do better than stirling

DHMO

@Sophie also, we already have 200!, so we don't need stirling

Sophie

200!=2^197×3^97×5^49×7^32×11^19×13^16×17^11×19^10×23^8×29^6×31^6×37^5×41^4×43^4×‌47^4×53^3×59^3×61^3×67^2×71^2×73^2×79^2×83^2×89^2×97^2×101×103×107×109×113×127×13‌1×137×139×149×151×157×163×167×173×179×181×191×193×197×199

so if 200! is the product of successive integers exactly one of them must be a multiple of 101, 103...199

DHMO

08:04

then what's the algorithm?

Sophie

I"m thinking about $n!=a!b!$ the difference $a-b$

DHMO

the difference would be very large

WLOG a>b

a must be above the last prime below n

Sophie

wait if $200!=a!b!$ then $a\geq 199$ because 199 is prime but then those cases are all trivial

DHMO

no, n is not 200!

that would be way too slow

I'm searching on b

so b is 200 instead

Sophie

I think searching on $n!$ is way faster than whatever it is you're doing that requires taking roots of stupidly large numbers

WiCK3D POiSON

08:10

Little help here--- Discrete function such that (1,2,3,....,n) --> (n,1,2,....,n-1).

For ex. (1,2,3,....,n) --> (2,3,4....,n,1) then f(i)=(i mod n)+1

Sophie

by the prime number theorem the average prime gap near x is $\ln(x+1)+1$ you only need to check around $\ln(x)$ possible combinations

DHMO

@WiCK3DPOiSON f(i) = (i+n-2 mod n) + 1

WiCK3D POiSON

@DHMO It satisfies. Thanks.

DHMO

@Sophie then the bottleneck would become the prime check

Sophie

I bet you're calculating primes over and over again

Dair

08:15

Maybe there is a less direct approach for calculating this?

DHMO

@Sophie hmm?

Dair

Dividing by $a!$ implies implies that you have $n(n-1) \cdots (n-a) = b!$

Sophie

@DHMO there are only like 70 primes less than 200, and 200! is already ridiculously huge. How far have you checked?

Dair

I believe that implies that $(n-a)$ is of the form $k!$?

Sophie

why?

DHMO

08:18

@Sophie you mean searching n?

Sophie

anything

DHMO

I have searched until n = 233200000

Dair

Well so: $n(n-1) \cdots (n-a)$ is of the form $b!$

DHMO

that's a separate program I ran earlier

Dair

now say that any other term is of the form $k!$

Sophie

08:19

@DHMO this is stupidly large. I don't think you're going to get anywhere near searching on b

Dair

then there would be an "overlapping" prime factor...

DHMO

@Sophie hmm...

I just need a better algorithm for n-root

Sophie

roots are large to extract and your numbers are big

DHMO

hmm...

Sophie

let $p_k$ be the biggest prime less than $n$ and $p_l$ be the biggest prime less than $n/2$. Then $v_{p_k}(n!)=1$ and $v_{p_l}(n!)=2$. Then if $n!=a!b!$ and $a>b$ then $a\geq p_k$ and $b\geq p_l$. Then the gap $p_{k+1}-p_k$ has to be somewhat large

and n has to be near $p_{k+1}$. In the $n=10$ solution that happens

Dair

08:25

I'm feeling like you can iterate through $a$ and determine if it $(n-a)$ is a factorial, then you have get $b$...

Sophie

and $a$ has to be near $p_k$

DHMO

@Sophie what is v?

Sophie

$v_{p_1}(p_1^{a_1}p_2^{a_2}\dots)=a_1$ where $p_1,p_2\dots$ are primes

so if $p_k!p_l!>n!$ there are no solutions

DHMO

can you use english to say it again?

Sophie

lol

okay so remember the factorization of 200!

it had a bunch of primes raised to 1

the primes between 101 and 199

so we determined that $a\geq 199$ because a must divide 199

no I'm wrong

DHMO

08:31

yes a >= 199

Sophie

what I've found is that there's no prime $p$ such that $n>2p>a$ but that isn't useful

DHMO

ok

Sophie

@DHMO how are you primechecking?

it shouldn't be hard to compute all the primes up to that number

DHMO

@Sophie trial division lol

I don't have that much space

Sophie

yes there's your problem. You can precompute all the primes, but there are algorithms which are fantastically faster than trial division

DHMO

08:36

ya i know trial division is a joke

Sophie

primes.utm.edu/lists/small/millions

all your primes. Bottleneck solved

DHMO

I don't have that many space

Sophie

yes you do. Learn to use it

DHMO

oh I know what I can do

I don't need to check if it is prime

I don't need that much trial divisions

Sophie

you only need to check up to the square root of the number, yes

DHMO

08:39

no

what I mean is

I don't need to check if it is prime

never mind

i'll use a sieve to see what i can do

Sophie

nooooo

you'll run out of memory

DHMO

how is that different from storing the primes?

Sophie

you don't store them all at once

DHMO

I see

Victor

Hi, anybody knows why the alternative advance level proof of fundalmetal theorem of calculus is taught at most graduate real analysis courses?

Sophie

08:43

don't they teach Stokes theorem?

DHMO

@Sophie thanks, I'll try later

Alessandro Codenotti

@DHMO whatever language you're using I'm pretty sure there are free libraries out there with an implementation of Miller-Rabin

DHMO

@AlessandroCodenotti ugh, Sophie's idea is better lol

Victor

@robjohn May you help with my problem above?

Sophie

Person 1: I'm going to grab this stick and poke 'em in the eye!
Person 2: No, shoot them instead
Person 3: Unleash the power of the atom!

robjohn

08:48

@Victor not even sure what you mean by "alternative advance level proof of fundalmetal theorem of calculus"

Alessandro Codenotti

The first 50 million primes are all well below 3000000000 so you only need to check 4 bases with Miller-Rabin (2,3,5 and 7), it'll probably be faster to recreate the files than downloading them

DHMO

@AlessandroCodenotti wow.

thanks

Victor

@robjohn The advanced proof refer to the measure theoretical proof of fundalmetal theorem of calculus

Starfall

fundalmetal?

robjohn

@Victor The measure theoretical proof has to do with the Lebesgue integral. That is used because measure theory is important to analysis.

Victor

08:53

@robjohn I wonder why it is taught while a more basic version of the theorem is already given in most undergraduate textbooks

robjohn

@Victor the non-measure theoretic proof is for the Riemann integral, not the Lebesgue integral.

Victor

@ robjohn Why people need lebesgue integral while riemann integral exist

Sophie

to integrate harder

robjohn

@Victor because it works in situations where the Riemann integral doesn't

Victor

@robjohn Is there existence for some case of single variable definite integral cannot solved by Riemann integral while lebesgue work in these cases?

robjohn

09:01

@Victor that's what I was just saying.

Alessandro Codenotti

Dirichlet's function

robjohn

@Victor The function that is $1$ on the rationals and $0$ otherwise.

Victor

@robjohn Thank you so much for answering. Please also take a look on math.stackexchange.com/questions/2078883/…

Please leave some comment if you are willing to

Alessandro Codenotti

Look up Risch algorithm, it's awkwardly big and I don't remember exactly its limitations, but you might be interested in it

Victor

@robjohn Had you lookup something before that is particularly useful for that question?

@AlessandroCodenotti Thank you so much for your reply. But do you know where can I lookup for its limitation

Starfall

09:24

@Victor the lebesgue integral is more robust

one problem aside from integrability concerns is that the riemann integral only makes sense when integrating over very specific sets

there was a nice question on the site some weeks ago which asked for a measure theory-free proof of the fact that if you have a bounded sequence of functions $ f_n : [0, 1] -> \mathbb R $ converging to $ 0 $ pointwise, then $ \int_0^1 f_n \to 0 $

you can assume the $ f_n $ are continuous, and take the integrals to be riemann integrals; it's still very tricky to prove this if you can't talk about the lebesgue measure

DHMO

@AlessandroCodenotti @Sophie primality test is still the bottleneck...

specifically, the modpow process is the bottleneck

kayak

09:55

@DHMO hi

DHMO

안녕 카얔

Ramanujan

Car?

kayak

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

Lollllll

@Ramanujan How do you know it says Car?

Ramanujan

@kayak Google translate :D

kayak

What did you type on?

카is sound like Car

Ramanujan

09:59

Google translate
안녕 카얔 To car

Transcript for

$Mathematics$ Mathematics