Mathematics - 2021-09-16

robjohn

12:02 AM

@TedShifrin It's pancreatitis. We need to get her eating and drinking. Using mirtazapine to get her appetite going.

@TedShifrin It's stressful. Some of that might have been responsible for my overnight at the local hospital.

Ted Shifrin

Oh my. I’m sure. Gosh. I’m sorry. :(

These last years are stressful for everyone. But hang in there!

copper.hat

@robjohn Sorry to hear it. It it tough all around.

Avra

1:11 AM

Hello,

copper.hat

hi,

Avra

@copper.hat. :/ Have you applied before Kruskals algorithm for minimum spanning tree please?

There are O(E) operations on the disjoint-set forest?

This is my question though

$E = \Sigma_v (v) = 2m$, where $v$ is vertex of graph and $m$ is total number of edges

copper.hat

a loooong time ago. what is your question?

Avra

@copper.hat. hahah :/

Wow. I am just looking to know why we got total $E$ disjoint operations when we sort edges before we start make unions, etc. to find out MST

copper.hat

1:39 AM

Surely you need $E \log E $?

Avra

@copper.hat. Thank you!

Why $E$ please?

What is your own interpretation as you understand it please?

No proof is needed

copper.hat

3:39 AM

You need to sort the edges surely?

Euler 2

4:14 AM

guthib.com

Koro

Suppose that the list of vectors $v_1,v_2,\cdots, v_n$ in vector space over field F is linearly independent. If $\lambda \in F$ is $\ne 0$ then is $\lambda v_1,...,\lambda v_n$ linearly independent?

For any $c_i$'s in F, if $\sum c_i\lambda v_i=0$ then $\lambda \sum c_iv_i=0$

And multiplying both sides by $\lambda^{-1}$, the result is readily observed to be true as all $c_i$'s will be forced to be 0

leslie townes

yeah, so by linearly independence of the v_i's, all the c_i's are zero, you win

Koro

But my question (confusion) is: when will characteristic $2$ create a problem?

leslie townes

it won't, for this

Koro

can you please give one example where char F =2 will create problem?

I have $u\in F$ then $u+u=2u=0$ so I can't conclude that u=0.

leslie townes

4:22 AM

for this result? i can't

2 is not a nonzero element of F

Koro

nevermind, I think I got it :)

leslie townes

there are places where characteristic 2 is different from other finite fields, with bilinear forms and quadratic forms sometimes you really want to be able to divide by 2

finite fields aren't ordered, which messes up stuff involving positivity, and they aren't algebraically closed, which means stuff like jordan form is going to be more complicated, just as it is in R

i'm sure there are clever ways to get to the same or similar results, but the proofs you tend to see in other fields won't immediately work

Koro

definition of a field is probably pretty much all I know about fields for now. i am yet to study jordan forms, billinear forms etc. :)

Semiclassical

4:38 AM

hmm. so i may be teaching an actual course this spring, not just doing TA work

and now my brain is switching gears from "oh yeah, this is a distant possibility" to "oh shit, this might actually happen"

Koro

@Semiclassical great :)

Ted Shifrin

5:06 AM

That should be more challenging , Semiclassic.

Koro

5:32 AM

I want to prove that vector space of all real valued continuous functions on $[0,1]$ is infinite dimensional.

Suppose on the contrary that $\displaystyle V$ is finite dimensional. There exist $\displaystyle f_{i}: R\to R 's\ ,1\leq i\leq n$, where $\displaystyle n$ is a fixed natural number such that $\displaystyle f_{i} 's$ is a linearly independent list and spans $\displaystyle V.$

For any continuous function $\displaystyle g\in V$, there exist unique real numbers $\displaystyle r_{i}{}_{g} \in \mathbb{R}$ such that

$\displaystyle g=\sum _{i=1}^{n} r_{ig} f_{i}$

I tried to repeat arguments as in my post here (math.stackexchange.com/questions/4251699/…)

but that won't work as set of all continuous functions on $[0,1]$ is of cardinality continuum.

I meant that there exist $f_i$'s such that $f_i:[0,1]\to \mathbb R$ are continuous functions.

leslie townes

indeed. it might be simpler to exhibiit an infinite set of linearly independent elements of C[0,1]

Koro

hmm

I somehow forgot polynomials.

The problem is solved now :) I always have 1,x,x^2,...

leslie townes

or, to avoid infinity, to produce for any n, an n-dimensional subspace of C[0,1]

and now you have remembered them :)

Koro

Thanks a lot Leslie :)

copper.hat

@Koro What about $f_n(x) = x^n$.

Or $g_n(x) = \sin 2 \pi n x$?

Koro

5:40 AM

that's what I said @copper. Indeed, $f_i(x)=x^i$ solve the problem. By the assumption of finite basis, $i\le m$ for a fixed natural number $m$. So the vector space is not spanned by the $f_i$'s hence $f_i$'s can't be a basis.

@copper.hat i didn't think of that. I'm not sure if it works. I'll think about this one.

leslie townes

if it's finite dimensional, so is its dual, and yet it's pretty easy to write down arbitrarily long lists of linearly independent linear functionals on C[0,1]

Koro

@leslietownes I'm yet to cover dual space, so I'll archive this comment for now :)

copper.hat

I meant $f_\beta(x) = \max( \beta x,1)$ for $\beta >0$.

leslie townes

i suppose it isn't 1000% obvious that the monomials are linearly independent. you do need to know that the zero function is only induced by the zero polynomial. not that it's hard to prove but it is often taken for granted

copper.hat

It is uncountable and straightforward (by differentiating) to show that they ar eli.

not just eli, but they are li.

Koro

5:51 AM

@copper.hat if these $g_i$'s are li (not proven by me yet) then $5=\sum r_i g_i(x)$ for all $x$ which is a contradiction as this does not hold when $x=1/2$.

it only remains to show that $g_i$'s are li

copper.hat

What $g_i$ are you referring to, the $\sin$s?

I have many sins/

Koro

@copper.hat yes

copper.hat

Where are you pulling the $5$ from?

Koro

$f(x)=5$ is a continuous function on $[0,1]$ so if $g_i$'s are basis of $V$ then one should be able to write $f$ as linear combination of $g_i$'s.

copper.hat

I never claimed that the collection was a basis, just that they are li.

You can show that any finite number of them are li, hence you cannot have a finite dimension.

But why not shoot for uncountable.

I am not even drinking yet!

Koro

5:58 AM

@copper.hat yeah, so if the are LI and V is finite dimension (supposing this on the contrary) with dim $n$ then $g_1,g_2,...,g_n$ are LI and this list is of right length (dim V=n, as we assumed on the contrary). But we know that $f(x)=5$ is continuous on $[0,1]$ so there must exist real number $r_i$ such that $f=r_1 g_1+...+r_n g_n$, that is $5=\sum r_i g_i(x)$ for all $x$, which is a contradiction as at $x=\frac 12\in [0,1]$, we have 5 on LHS and 0 on RHS.

So our assumption that V is finite dimensional is wrong.

leslie townes

i'm not sure that it's possible to 'write down' a linear algebra basis for C[0,1]. 'write down' meaning, without appealing to AC or something.

linearly independent sets are by contrast easy to find.

copper.hat

@Koro I think you can just suppose $\dim V = n$ and pick $n+1$ li elements $g_k$ and then conclude a contradiction.

Koro

yes, that's also fine :)

copper.hat

Arguing that countable set is a basis is likely to get your hand slapped...

Or bitten by an angry hamel in the desert.

I need some wine. A Hamel basis is a what a basis is called in an infinite dimensional space.

To distinguish from other sorts, such as Schauder.

Koro

@copper.hat oh my God 😅

leslie townes

6:04 AM

i call them linear algebra bases. i suspect hamel would be embarrassed by his name being associated with that.

Koro

I think you meant camel? @copper

copper.hat

the basis of truth

leslie townes

like people calling the indicator function of the rationals the dirichlet function or weierstrass function or whatever they call it.

copper.hat

it was a bad play on words. i excel at bad plays on words.

that is a characteristic of indicators with no character

leslie townes

some things don't need to be named after people. i feel very strongly about this. for more, consult the 3 hour episode of my podcast, leslie speaks, on this issue.

copper.hat

6:06 AM

wow, that could be deep if you smoked the appropriate substance

it is handy to have a name, albeit we all know that the name rarely tells the truth.

complete normed space does not have the haughty ring of banach

and hilbert. almost a cartoon.

leslie townes

we can have banach spaces. a list of acceptable things named after people appears around the 2:30 mark in the podcast.

copper.hat

ok, i must go and prepare for my son's departure.

my wife & daughter are heading to la (yes, the real la) next week so i will be in truly pitiful shape next week.

leslie townes

i was pretty deep in the bag by that point, it's mostly me just reading off names of things while you hear ice cubes clinking against glass in the background. the last 15 minutes are me snoring.

good luck with all of that.

copper.hat

breaking every shred of irishness i have, i told my son that i would miss him. he looked at me as if i had blown a noseful of covid snot in his eyes.

leslie townes

i hope you pummeled him with a coal shovel to sort of even out the universe a little.

copper.hat

6:10 AM

i am ready for a clinking ice cube.

just one sentence without a f** typo, ffs.

there, the only such sentece

i have only hit each of my children once, hard.

when they bit my stomach and drew blood.

while drying them after their bath.

through my t-shirt (in case tsa/cps are listening)

suddenly it all became clear to copper

Euler 2

vs code vs vim

leslie townes

i guess you didn't have some garlic or a cross handy.

copper.hat

the hatred, the snide remarks, no slippers and cool beers for dad as he gets home from a grueling day in the basement.

vimffs

vs code is for people who like visual silliness

microsoft programmers and the like

Euler 2

console ❤❤❤

copper.hat

the like the look of a blue screen

damn it, i used to flip switches on a pdp8

no namby pamby ascii rubbish.

Euler 2

6:15 AM

$ touch con

copper.hat

unicode is a good example of what is wrong in the world with all these woke symbols.

Euler 2

mathematica vs matlab?
vs make your own

copper.hat

def not mathematica

at least matlab started with fortran

before degenerating into c/c++

Euler 2

"degenerating"

copper.hat

c: the power of an assembler with the readability of an assembler

c++: bjarn on some form of hallucinogenic drug

i need some legal ssistance

what does libel mean?

ok. there are folks here who want to talk to me about something. good night folks!

Koro

6:23 AM

Good night @copper. Thanks for helping me today :)

copper.hat

@Koro I suspect I was more noise than help, but I appreciate your words :-)

Bye

Koro

@copper.hat no, that $g_n$ example helped and is also an exercise for me (as I said, I've not yet proven $g_n's$ to be LI yet) :)

Koro

6:59 AM

$g_i$'s are indeed LI because $\{g_i: 1\le i\le n\}$, where $g_i(x)=\sin (2i\pi x)$ is an orthogonal set over $[0,1]$.

BannedUser

7:17 AM

Is runtime cost of recursive Fibonacci related to golden ratio?

To me it seems somewhat exponential.

JamalS

8:00 AM

When we write $H^2(G,k^\times)$ what is the implied action on $k^\times$ normally?

As in the one that makes $k^\times$ a $G$-module

Thorgott

11:03 AM

that's a very open-ended question

context might help

JamalS

11:51 AM

Isn't there a default assumption? I think it's suppose to be the trivial action?

user193319

12:22 PM

Suppose $f$ is holomorphic on a neighborhood of $\overline{B(z_0,r)}$, where $z_0$ is a zero of $f$. If $f$ is identically $0$ on the boundary of $B(z_0,r)$, does it follow that $f$ is $0$ on the whole disc?

Is this just an application of the identity theorem?

Thorgott

it's hard to make default assumptions in the absence of context

if $G$ and $k$ have nothing to do with one another, this is bizarre and nothing but the trivial action makes sense, but usually expressions like that come up within a context such as Galois cohomology when $G$ is a Galois group acting on $k$ or something of the sort..

user193319

Hmm...the assumption that $z_0$ is a zero doesn't seem necessary...

Thorgott

@user193319 yes

you can also argue using Cauchy's integral theorem

user193319

Ahh, interesting. Thanks!

Thorgott

if you know the stronger version thereof, it actually suffices to assume $f$ is holomorphic on $B(z_0,r)$ and continuous on $\overline{B(z_0,r)}$

user193319

12:29 PM

Oh, that makes sense. Thanks for pointing that out!

Avra

1:19 PM

Why resizing array with the following sequence $3k, 5k, 7k, 9k, ... $ for some positive constant $ k$ is more intuitive than $2k, 4k, 8k, 16k, ... $ please? Here we resize an array one it gets full by either of the sequeces. You can only follow on of the sequences, however, $3k, 5k, 7k, 9k, ... $ is recommended as it it adopts to higher frequency of add calls to array. What do you think please if you have any thought?

Semiclassical

1:33 PM

Trying to figure out what the “usual” terminology for this. Suppose I’ve got an (ordered) list of N distinct elements. Then the identity permutation is obviously the only one which leaves the list unchanged.

Now suppose some of those elements are identical. To be precise: n1 are type 1, n2 are type 2, and so forth

Then the number of permutations which leave the list unchanged are n1! n2!…

Avra

@Semiclassical. Thank you, but here, I am looking to see as to why the 3k,5k,7k,9k,... sequence is a better choce to consider when array is full and you want to resize it (increase size to acoomodate new elements once it's full)

Semiclassical

Um

I wasn’t talking about your problen

Avra

:/

Sorry

It was very close though

Semiclassical

I’ll take your word for it

Avra

:/

Anush

2:15 PM

imagine you have a sequence of positive integers and positive or negative counts in pairs. E.g. (2,3), (1,-2), (2,-2), (1,2) which means 3 twos, -2 ones etc. I want to know if there any of the integers end up with a non-zero count. In this case 2 gets count 1 and 1 gets count 0 so the answer is yes. if I just let c equal the sum of the counts and z equal the sum of the product of the integers and counts I get c = 1 and z = 2

to answer my question about whether any of the integers have non-zero count, is it enough to check of c = z = 0?

porridgemathematics

2:52 PM

is the following true? let $D_1,D_2 \subset \mathbb{C}$ be domains, and suppose $f : D_1 \rightarrow D_2$ is a conformal isomorphism , let $\gamma$ be a closed curve in $D_1$ and $a \notin Im(\gamma)$ a point in $D_1$, then $n(\gamma,a) = n(f \circ \gamma, f(a))$

if $f$ is just a conformal map this is false

Thorgott

3:46 PM

I forgot what a conformal isomorphism even is, but an orientation-preserving homeomorphism will suffice

porridgemathematics

4:29 PM

@Thorgott its just a biholomorphism

im able to see this when $\gamma$ is null-homotopic in $D_1$, using the argument principle.., whats the proof for $f$ an orientation preserving homeomorphism

also im not assuming $\gamma$ need be $C^1$ or even rectifiable

just needs to be continuous

Thorgott

5:40 PM

I realized I don't have a particularly convenient argument, but here is a way to go about it: $D_1\setminus\{a\}$ is an open subset of $\mathbb{C}$, hence contains a bouquet of circles onto which it deformation retracts. A small deleted neighborhood of $a$ will be contained inside exactly one of the circles in the bouquet, for otherwise it would be contractible. This furnishes a retraction from the free group $H_1(D_1\setminus\{a\};\mathbb{Z})$ to a direct summand. The loop $\gamma$ defines an element of $H_1(D_1\setminus\{a\})$, which maps to its winding number (upon identifying $H_1(S^1)\…

sorry, this isn't lucid at all, but this problem turns out trickier than I was thinking..

cOnnectOrTR 12

6:54 PM

Hi everyone!
I read deltafx is equivalent to (df/dx)delta x. So are both of them same thing only the df/dx is a more accurate. And both are rates like charge per unit area or distance per unit time.

df/dx is also some physical quantity per unit some physical quantity ?

Avra

7:33 PM

Hello,

If we have a triangle where all edges have same weight, then can we have a cut where all edges are crossing edges please?

I believe that this is a valid cut and all edges are cross edges, is that correct please?

copper.hat

this looks like one of those diagrams in a high school biology book.

leslie townes

it's the krebs cycle

avra, this may be more my lack of background than anything else, but what is a 'cut' and what does it mean for edges to have the same weight

is this some standard thing that appears in the middle of some proof of some graph theory algorithm i guess just ignore this

Avra

@copper.hat. Hahaha

The red path is the cut

So, we can not here have Minimum spanning tree just by relying on light edges (minium crossing edges weights), so having all light edges does not guarantee that we will get MST.

That is what I was trying to prove :/

Thank you anyway

weight of edges is a natural number indicating a value for edge

light edge is supposed to hold the minimum weight and it must be a crossing edge too

leslie townes

7:53 PM

avra, forgive my ignorance, but what is it about a 'cut' that makes what you've drawn different from what you'd get if there was just a straight line between the endpoints of your red curve

Avra

8:47 PM

@leslietownes. Appreciate your responses. This is from the question, that all edges are a cut edges, so the read line (cut) has to go through all of them

This is how I understand it :|

leslie townes

what is the significance of a cut going through an edge?

Semiclassical

9:19 PM

@Avra I do know a bit about this (it’s related to the classical aspect of Bell’s inequality) and what you should notice is that your cut crosses the bottom edge twice

As such, it’s equivalent to not having a cut over that edge at all

leslie townes

this is what i was wondering. if the purpose of the cut is to separate the graph into two pieces, the two lower vertices seem to wind up in the same piece. so i'm wondering if there is more to a 'cut'

Semiclassical

The rule that I’d give: if both nodes belong to the same subset, there’s no cut for their edge

Another way to put it: assign plus / minuses to the nodes, and label each edge with the product of these signs

No matter what you do, you’ll never end up with an odd number of minuses on the edges

You can have no cut edges or two cut edges, but not one or three

If you do it on a 4-cyclic graph, you similarly can only get even number of edges being cut

This leads to some nice polytope stuff, eg, mathoverflow.net/a/128809/55904 @leslietownes

And the facets of those polytopes are Bell inequalities

Avra

9:45 PM

@Semiclassical. Thank you!

@Semiclassical. Have you studied graph theory before please?

@leslietownes. Very sharp. Thanks. Yeah a cut produce a cut, so I made mistake up there, sorry

Semiclassical

Not a lot, but I have run into how cut graphs relate to Bell inequalities

It’s sorta cute. Suppose, according to some distribution, you picked a partition on a graph

And assign -1 to an edge that’s cut, and zero otherwise

We can then start to ask statistical questions, eg, what’s the expected value of a given edge

And in this way you find inequalities. For instance, suppose you add the values together that you get from the three edges in a 3-cycle

A priori, each value is just some number between -1 and 1, so their sum must be between -3 and 3

But because you can only get an even number of cut edges, the lower bound is actually -1 not -3

And this in essence is bell’s original inequality :)

(Nowadays one usual does this for the cyclic graph on 4 nodes rather than 3.)

Avra

11:43 PM

@Semiclassical. Wow!

That is really interesting

Any idea how we can detect that we have odd cycle of a graph (odd number of vertices) using the fact that we store the length of a path at each vertex as we traverse the graph as $d[v]$. So, the equation to detect if we have an odd cycle is $if(d[u] \bmod{2} == d[v] \bmod{2})=> Odd Cycle$

Transcript for

$Mathematics$ Mathematics