Mathematics - 2021-09-07

shintuku

00:02

but uh, it's not a very popular suggestion

SmokenSieEinBitteChebaHitBits

@geocalc33 hey

Ted Shifrin

00:14

You live(d) in Boston, @shin?

Tyma Gaidash

How is this about Mathematics?

leslie townes

general discussion will do until some math comes along. maybe even after that, too.

copper.hat

Life is mathematics.

Balarka Sen

A typical example of a non-Hausdorff manifold is $\Bbb R \times \{0, 1\}/(x, 0) \sim (x, 1)$ where $x < 0$. This picture of a "branching" can be repeated to produce new non-Hausdorff manifolds out of old ones, eg take two copies of a manifold $M$ and $N$ and paste them along open inclusions $U \to M$, $U \to N$.

shintuku

@copper.hat Leibniz please refrain from leaving the realm of the dead, people start asking questions

Balarka Sen

00:26

This picture is general enough that it deserves a name. I think people call the example I gave a "branching real line", but that makes it sound like $\Bbb R \times \{0, 1\}/(x, 0) \sim (x, 1)$ where $x \leq 0$, a nonmanifold

What's a good name? Feathering, perhaps?

For example, a typical place where this occurs is sheaves. Take the constant Z/2-valued sheaf $F$ on a subset $A \subset X$ of a space $X$, and consider $(\iota_A)_*F$, it's leaf space over $X$ is $X \times \{0, 1\}/(x, 0) \sim (x, 1)$ where $x \in \overline{A}$.

More complicated behavior occurs on $\partial A$ if $F$ wasn't constant over $A$... but there's still a "foliation with leaves merging together like a feather"

Ted Shifrin

I always called this the line with two origins.

Not quite your example .

Balarka Sen

That's $\Bbb R \times \{0, 1\}/(x, 0) \sim (x, 1)$, $x \neq 0$ to me. Alternatively, leaf space of $(\iota_0)_*\underline{\Bbb Z/2}$, Z/2-valued skyscraper at $0$

In my opinion sheaves are a major generalization of the line with two origins :)

Also a good example is a locally constant sheaves; these are just foliated bundles. The "leaves" do not merge, so there is no feathering behavior.

Also I guess you could talk about, for any $A \subset X$, the compactly supported pushforward $(\iota_A)_! F$, which is basically $(\iota_A)_* F$ but stalks are zero on all points of $\partial A$. So it's very much $X \times \{0, 1\}/(x, 0) \sim (x, 1)$ where $x \in \mathrm{int}(A)$ if $X$ is locally compact Hausdorff, say.

Balarka Sen

00:52

I guess also of interest is $f : \Bbb R \to \Bbb R/[0, 1] \cong \Bbb R$ quotient map, $F$ Z/2-valued skyscraper at the image point of $[0, 1]$ in the target, $f^*F$ is $(\iota_{[0, 1]})_*\underline{\Bbb Z/2}$.

if $f : X \to Y$ is a map, $F$ a sheaf over $Y$ and $G$ a sheaf over $X$, $Hom_X(f^* F, G) \cong Hom_Y(F, f_\star G)$ is the usual duality. Here's a reinterpretation in terms of the above picture: the leafspace of $f^*F$ is the trivial foliated bundle over the fibers of $f$ and $F$ transverse to the fibers of $f$, so morphisms $f^*F \to G$ over these fibers (thus germs of saturated nbhds of these fibers) are determined by maps $F \to f_* G$

DanielSank

01:38

I'm trying to find the asymptotic behavior of the following integral:

$\int dx x^2 p(x) \exp(-a |x|^\beta t)$

What methods can help?

Here $p(x)$ is a probability density function and $\beta > 1$.

The integral is over $\mathbb{R}$

Ted Shifrin

Look up the method of stationary phase.

DanielSank

@TedShifrin That was the first thing I thought of. What I fail to comprehend is how to apply it in this case where the function in the exponent doesn't have a maximum.

Oh I'm silly.

Ted Shifrin

Hmm, maybe I am misremembering. There’s no oscillation.

Look maybe at a Taylor expansion about the max of the integrand.

DanielSank

yeah I think "stationary phase", "saddlepoint", and "Laplace's method" are all the same thing and all relevant here.

Ted Shifrin

01:54

Without an $i$ in the exponential, it doesn’t have phase. :)

DanielSank

Right, but "stationary phase" means you find a path where the phase is stationary, and then use Laplace's method.

I think Laplace's method is what we need here.

Laplace's method

In mathematics, Laplace's method, named after Pierre-Simon Laplace, is a technique used to approximate integrals of the form ∫ a b e M f ( x ) d x , {\displaystyle \int _{a}^{b}e^{Mf(x)}\,dx,} where f ( x ) {\displaystyle f(x)} is a twice-differentiable function...

Ted Shifrin

Yeah, I taught this stuff in 1987, so I’ve forgotten,

DanielSank

Eh, or not since the thing in the integral isn't even continuous.

I think expanding near $x=0$ is the ticket.

Ted Shifrin

Everything here is continuous?

DanielSank

$|x|^\beta$?

Ted Shifrin

01:58

Smooth, in fact.

Certainly $C^1$, as $\beta> 1$.

DanielSank

Interesting. It seems that for $\beta > 2$, all order derivatives of $\exp(-a x^\beta t)$ at $x=0$ are zero.

DanielSank

02:23

@TedShifrin we're thinking too hard. You can get the asymptotics just by variable substitution!

Snapdragon-X

06:38

The math community bot can talk now?

Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. — Community ♦ 11 mins ago

mohamed azaiez

07:58

Hi,I am kinda of a noob so bear with me pls,I can't really make this into a question so i am just gonna ask it here,
I was looking to understand more about basic math like operations (addition multiplication) and I was wondering how these are actually defined, For example if we take addition is it defined by a list of properties or is it like an instruction that like maps a value into an other and the list of properties are just describing it,I read somewhere that addition is just repeating the incrementing operation x times from this view addition now really feels really simple to describe…

robjohn

08:34

@mohamedazaiez They are all correct, where they apply. You can look at it in any way that makes sense in a given situation. For example, you can't look at .23+.42 as incrementing .42 times, so you have to look at addition of rational numbers (decimal fractions are rational numbers).

Don't ask, "should I look at it like this, or like this" and then come back later and say, "oh, I did what you said and it didn't work in this case." Think and decide for yourself.

Build and exercise the thinking part of the brain. The regurgitation part of the brain is useful, but not the only part that is needed.

I'm sorry, but I don't have a good text or reference, but Wikipedia under Addition and Multiplication might be a good place to start.

The Testosterone Fanatic

13:51

would anyone familiar with support vector machines be willing to solve this problem?

https://cs.stackexchange.com/questions/143752/why-is-quadratic-programming-used-to-the-solve-support-vector-machine-optimizati

user193319

Let $\Omega \subseteq \Bbb{C}$ be open. I have biholomorphic functions $f,g : \Omega \to \Bbb{C}$ satisfying some hypothesis, from which I was able to conclude $|f(z)| = |g(z)|$ for every $z \in \Omega$. Why does this imply there exists a unit complex number $c$ such that $f(z) = cg(z)$? Which theorem allows me to conclude this?

Edward Evans

$|f(z)/g(z)| = 1$

rschwieb

Question for commutative algebraists: In this wiki article it seems like the terms J-0 and J-1 are defined such that a J-1 ring might not be a J-0 ring (in the case where a J-1 ring has an empty set of regular points, and is hence not J-0). Does anyone know if that is intentional? Or should the wiki definition for J-1 read "the regular points form a nonempty open set"?

user193319

14:08

@EdwardEvans Ah, okay. So, I have that $f(z_0) = g(z_0) = 0$ for some $z_0 \in \Omega$. So, $|f(z)/g(z)| = 1$ for every $z \in \Omega \setminus \{z_0\}$. Hence, for every such $z$, there exists $\theta_{z} \in \Bbb{R}$ such that $f(z) = e^{i \theta_{z}} g(z)$...But how do I show that $\theta_{z}$ is a constant?

Thorgott

15:05

something about bounded entire functions

copper.hat

15:25

open mapping theorem perhaps?

love_sodam

15:40

0

Q: Intersection of two simplices is a convex hull

My definition of $d$-dimensional simplex (also called $d$-simplex) is a convex hull of $d+1$ many points in $\Bbb R^d$ (or larger space) which are affinely independent. Also, a face of a simplex is a convex hull of arbitrary subset of vertices of a simplex $\sigma$. Currently, I'm proving the tri...

need a little help here

user193319

@copper.hat Apply the open mapping theorem to $f(z)/g(z)$? The only problem I see is that $\Omega \setminus \{z_0\}$ won't be a domain, right...?

robjohn

@user193319 maximum modulus principle says that if the maximum modulus is attained internally, the function is constant. $f/g$ is holomorphic and $|f/g|=1$ everywhere, so $f/g$ attains its maximum modulus internally.

@user193319 $z_0$ is a removable singularity of $f/g$ since $|f/g|$ is bounded

user193319

15:57

Ah, so it can be redefined in such a way that $|f(z_0)/g(z_0)| = 1$?

robjohn

or more precisely, so that $f/g$ is holomorphic

user193319

Okay, let me write all this up. Thanks!

AMDG

16:37

Long time no see, guys.

user193319

I have a holomorphic function $f(z) = \sum_{k=0}^{\infty} a_k z^k$ on the unit disc with $|f(z)| \le 1$ for all $z$ in the unit disc. I want to show that $|a_k| \le 1$ for all $k \ge 0$. I want to use the Cauchy estimates, but the only problem is that I don't know if $|f(z)| \le 1$ for $z$ on the unit circle.

Is there a way of applying the Cauchy estimates or is there some other method?

AMDG

@PM2Ring Surely, there is more to waveform composition than just fourier transform, no? I am interested in understanding waveforms that are more complicated yet only ever oscillate between two values. Can fourier tell me how to decompose a waveform that has a specific repeating sequence into a function of various elementary waveforms such as sine, triangle, square, sawtooth, and so forth using any set of elementary operation?

Thorgott

16:55

the unit circle is contained in the unit disk

user193319

17:12

@Thorgott Sorry, I mean the open unit disc, so $\Bbb{D} = \{z \in \Bbb{C} \mid |z| < 1\}$ is the open unit disc.

Thorgott

ok

still, use the Cauchy estimates

the unit disk isn't the only disk on which they work

user193319

Oh...so just take a smaller disc contained in the open unit disc and apply the same analysis. Gotcha! Thanks!

@Thorgott Hmm...maybe I'm missing something, but I don't see how that helps. If $\rho \in (0,1)$, then $f$ is analytic on $\{z \in \Bbb{C} : |z| \le \rho\}$ and $|f(z)| \le 1$ for all $|z| \le \rho$. So, the Cauchy estimates tell us $|f^{(k)}(0)| \le \frac{k!}{\rho^k}$. Since $f^{(k)}(0) = k! a_k$, we have $$|a_k| \le \frac{1}{\rho^k}...$$Hmm...

Thorgott

so what happens if these circles get closer to the unit circle

user193319

Oh...shoot...d'oh. So just take the limit as $\rho \to 1$...

Ted Shifrin

17:37

@Thorgott But not entire.

Thorgott

it is entire

the singularities are all removable by Riemann

Ted Shifrin

I thought the domain was $\Omega$.

Oh, biholo to $\Bbb C$.

I wonder if he really means that.

I doubt it.

Thorgott

17:57

the only domain biholomorphic to $\mathbb{C}$ is $\mathbb{C}$, so yeah, this set-up is weird

Ted Shifrin

I don’t believe the intent is surjective to $\Bbb C$.

copper.hat

18:17

i think more time is spent clarifying questions than answering...

AMDG

The story of my (professional) life

robjohn

@copper.hat and let me tell you why...

copper.hat

i need that clarification :-)

o.9

helloni

robjohn

I have just been in a deep depression about the recall election this morning. The polls are in favor of denying the recall, but the margin is just so slim.

o.9

18:21

slim and shady?

AMDG

I regret making this custom hot chocolate. It turned out poorly.

This is what happens when you don't learn integral calculus, kids.

copper.hat

regardless of one's politics, the recall is disturbing.

Ted Shifrin

Verily.

robjohn

@AMDG Integral calculus helps make hot chocolate?

AMDG

@robjohn It's a bad joke. You need to mix the correct ratio of volumes, and the volume of the container must be known. I don't know the ratio, nor the precise volume of the container for water with alkaloids (and other related cocoa substances), nor am I aware of the best emulsifier to ensure that the consistency is correct and there is uniform density and distribution of cocoa and other potentially dissolved solids like sugar.

"See! Integral calculus in daily applications!"

o.9

18:36

in dairy applications

AMDG

"...thus we conclude that the volume of a ten gallon hat is in fact not ten gallons"

Anyways, anyone know much about waveform analysis concerning what I mentioned earlier? I asked around on IRC and was given Hadamard transform as a potential answer, and it looks promising!

robjohn

Integration around polls can affect results at election time...

o.9

around poles ?

robjohn

it's an election time joke...

o.9

it's a good one

AMDG

18:45

I don't understand it therefore it must be a bad joke. :P

robjohn

@AMDG must be hard to be you ;-)

AMDG

You can't imagine

Looking for new algorithms is fun yet exhausting. Certainly one of the few things that has been a challenge to me. Mostly because everything else just requires explaining.

The only pain is when I come across papers that use terminology I don't yet understand. I can read more of them now quite painlessly, but much beyond what I've been looking into a lot myself is quite difficult.

I think the worst part, though, is reading someone else's weird syntax design for some pseudocode that is in no way intuitive at all.

May as well be written in standard galactic.

So yeah, these knowledge gaps in terminology are what effectively end up making me just figure things out on my own instead of reading papers, and watching YT videos by the likes of Mathologer and 3b1b which describe things in a manner that is more simple and easy to understand. Video arXiv submissions when.

robjohn

@AMDG The syntax is easy, but the vocabulary is so localized.

AMDG

Yeah, exactly, or the ordering of tokens might make things ambiguous. It's like claiming that little endian is more intuitive to grasp compared to big endian which is obviously false. FIte MeH.

I kid you not, I understand little endian well and it still messes with my head whenever I try to do arithmetic or processing with it.

AMDG

19:19

I came across wikipedia mentioning that you can compute exp ln and circular functions using AGM. How is that done?

robjohn

@AMDG the bits are little endian, bit 0 is the low order bit, so why change when it comes to bytes in a word (etc), byte 0 should be the low order byte. The 6502 was little endian and the 68000 processors were big endian. As I remember, when the processor wrote out a word, of whatever size, they were swapped appropriately, if needed.

so it was not a problem unless you tried to read a word as bytes. Then you needed to be aware of the endiannes

Semiclassical

@AMDG looks like there’s a whole book on this: “Pi and the AGM” by Borwein and Borwein

AMDG

@robjohn What do you mean by the bits are little endian? What I'm trying to say is that what we are all taught in school is big endian base 10, with most other bases written big endian order, so we come out with big endian feeling quite natural.

Semiclassical

Also these slides : maths-people.anu.edu.au/~brent/pd/JBCC-Brent.pdf

AMDG

Come along computers and binary and the architectures you mentioned, and suddenly we have this introduction of endianness.

Semiclassical

19:29

Which do have some details on computing log via AGM

(I make no guarantees about whether said slides can be understood!)

AMDG

@Semiclassical That's good, I can compute arctan that way, but what about exp? (Not strictly important to me given that I can do that efficiently using a small handful of taylor terms, but would be nice to know).

PM 2Ring

@AMDG Every periodic waveform can be represented as a Fourier series, even square waves (although to represent a square wave perfectly the Fourier series needs an infinite number of terms).

Now Fourier probably isn't ideal for whatever it is you want to do with your square waves (assuming those waves even have a well-defined period). However, as I tried to explain before, you will have a hard time reading the literature in the field of wave / signal analysis if you aren't comfortable with the basics of Fourier.

AMDG

@PM2Ring Yes, I am seeing that already. Do you know of a quick overview of Fourier as a cheatsheet that I could look at?

robjohn

the low order bits are the lower numbered. Just because we write strings of bytes ascending from left to right in memory, but ascending digits, bits, bytes in a word as increasing right to left, doesn't mean that it is more logical to swap the order of significance of bytes in memory to match our inconsistencies.

AMDG

I watched a 3b1b video on it and I gather that it effectively computes the frequencies for which a function is composed as a sum.

However, with my limited understanding of its true substance, I cannot say that it is useful, then, beyond identifying waves of a discrete number of frequencies that are summed together.

copper.hat

19:33

@AMDG At some level the Fourier series is just a representation of an $L^2[0,1]$ function in a particular basis.

robjohn

@copper.hat a fourier analyst would say $L^2$

copper.hat

@robjohn Oops, that was my intent.

There's also Walsh functions.

AMDG

What does $L^n$ notation mean?

copper.hat

Measurable square summable functions. Well, $L^2$ at least.

PM 2Ring

@AMDG Not really. I learned this stuff in a fairly disorganised way. You need to know a little bit about Fourier in terms of integrals. But for computing applications, you'll mostly be dealing with the Discrete Fourier Transform. And the entry-point for that stuff is the complex roots of unity.

robjohn

19:36

Rademacher system

In mathematics, in particular in functional analysis, the Rademacher system, named after Hans Rademacher, is an incomplete orthogonal system of functions on the unit interval of the following form: { t ↦ r n ( t ) = sgn ⁡ ( sin ⁡ 2 n + 1 π t ) ; t ∈ [ 0 , 1...

copper.hat

i was going for completeness :-)

AMDG

Yay, more knowledge.

robjohn

Hadamard transform

The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal, symmetric, involutive, linear operation on 2m real numbers (or complex, or hypercomplex numbers, although the Hadamard matrices themselves are purely real). The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2. It decomposes an arbitrary...

AMDG

Yep, that's what I was given in IRC.

copper.hat

@AMDG What do you want to use Fourier series for?

robjohn

19:39

they're cool

AMDG

Well apart from implementing fourier as part of a standard library, I want to compute some function of the frequency of a square wave over time where the amplitude oscillates between two constants that may be multiplied by some other constant.

And ideally said function would be a closed form consisting of elementary operations and elementary waveforms whose frequencies and amplitudes are constants.

And the number of terms discrete.

copper.hat

Ihave no idea how that relates to Fourier series,

AMDG

Me neither lol

copper.hat

Or what it means to implement Fourier.

AMDG

But if Hadamard transform is related to it (since that is what was given to me to look at), then it is related to Fourier.

To implement an algorithm is to create a program that computes the given algorithm to some specified precision.

PM 2Ring

19:45

@AMDG en.wikipedia.org/wiki/Arithmetic%E2%80%93geometric_mean has some info about using AGM to compute elliptic integrals. Sorry, I only vaguely understand this stuff, but I have written code that uses AGM to compute the period of a pendulum (i.e., without using the sin(x)=x small angle approximation).

copper.hat

thanks, i think i understand the word algorithm :-).

PM 2Ring

I also wrote this Python program that uses the AGM to compute large numbers of digits of pi. stackoverflow.com/a/26478803/4014959

AMDG

@PM2Ring I was introduced to the application of AGM and what it is from Matt Parker. youtu.be/gjtTcyWL0NA

PM 2Ring

19:59

One very common use of DFT (well, really the discrete cosine transform, which is closely related) is in JPEG compression. It breaks the image into 8×8 pixel blocks & transforms the block data into frequency space, using a 2D DCT. That's a fundamental factor in why JPEG can get such high compression ratios without losing too much image quality.

It essentially simplifies the high frequency components of the image, which reduces the entropy considerably.

AMDG

Ah, ok

copper.hat

20:17

it also means that you can progressively update the image over time easily

just to be clear, the dft is lossless, the decision to drop higher 'frequencies' is what allows compression.

PM 2Ring

Well, you'd (generally) get some compression from the Huffman encoding, but of course a perfectly lossless compression scheme cannot always reduce the file size, due to the pigeon-hole principle.

AMDG

pigeon hole principle is modulus in substance

copper.hat

or a law of averages

AMDG

Can't see it

Oh wait I see now

copper.hat

i think of the pigeon hole principle as a ceiling on an average :-)

Mikestylz

20:27

The textbook I'm using introduced projections and began using projections without much explanation of their properties so I tried to determine some of them on my own. I have a somewhat informal proof that since a projection must be equal to the identity operator on its image, each column must be either an "identity column" consisting of all zeros except a 1 at the diagonal, or an "irreversible column" which can have nonzero values only at rows J such that the columns J are identity columns.

Is this a correct result?

Also that use of the pigeon hole principle with compression is quite lovely

AMDG

@PM2Ring I would not be so inclined to state that an optimal lossless compression scheme cannot reduce size in all situations. If the data is the result of a deterministic process, the process itself is the optimal lossless compressed form together with the function of its inputs. For entropy or arbitrary data, arbitrariness still relies on the natural order for the existence of its applications.

That being said, even in the worst case of a data set with entirely unique values, it can be decomposed into self-similar parts because it is composed of self-similar parts, and from those parts, patterns can be deduced, because by the pidgeon-hole principle, I would conjecture that any finite field (?) must have repeating patterns. To get something incompressible, it needs to be infinite and each element of the set must be fundamentally unique in all aspects, conceived or inconceived.

In other words, I would claim based on this naive hypothetical that there is only one incompressible set, the set of all entirely-unique objects which would probably have to exclude itself as a member of this set for it to be truly incompressible.

Good thing most things we use in the material universe are usually made of a single particle built upon itself :D

AMDG

20:54

I'll be back later. I need some recreation.

Avra

21:11

Hello,

I am not sure if this question is valid, but does having $p$ as a prime number suggest anything when we have $p \bmod{m}$ please where $m \in \mathbb{Z}$?

PM 2Ring

@AMDG Um, no. Compression is generally useful because data that we're interested in normally has lots of redundancy, and we've invented / discovered some clever ways to capture that. But you can't compress everything. Eg, try compressing the image in my answer here: unix.stackexchange.com/a/289670/88378 which is composed from bytes pulled from /dev/urandom

Avra

If the greatest common divisor of two numbers is 1, then both numbers are relatively prime I can say please?

Ted Shifrin

@Mikestylz No, not unless you compute the matrix with respect to the right basis. I recommend a better book :)

@Avra That’s the definition.

Avra

@TedShifrin. Thanks Prof

PM 2Ring

@Avra I don't know what you're trying to say. But consider, 13 is prime, but $13 \equiv 4 \pmod{9}$ and 4 isn't prime.

Avra

21:22

@PM2Ring. Thanks. Here 13 is a prime but 13 and 9 are not coprimes

13 and 11 are relatively primes

PM 2Ring

Of course they are. What common factors do 13 & 9 have?

Avra

gcd(13, 9) = 1

Mikestylz

@AMDG I think that a look at Chaitin's Incompleteness Theorem will be enlightening (en.wikipedia.org/wiki/…)

Avra

So, 13 and 9 are relatively primes

PM 2Ring

That means they are coprime.

Avra

21:24

I just had a proof

It's complex, so I am trying to understand it piece by piece

Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_i(k) + ih_2(k)) \bmod{m} $. Show that the probe sequence $<h(k, 0), h(k, 1), \cdots , h(k, m - 1)>$ is a permutation of the slot sequence $(0, 1, ... , m - 1)$ if and only if $h_2(k) $ is relatively prime to $m$. (Hint: See Greatest Common Divisor (GCD))

robjohn

@Avra 9 and 13 are coprime

@Avra primes are distributed over all equivalence classes mod $m$ that are relatively prime to $m$.

Mikestylz

@TedShifrin what books would you recommend instead?

I like reinventing bits of the theory as I go and predicting what directions the proofs will take. It is the best way for be to build intuition on a subject

Avra

@robjohn. Relatively prime and co-prime is same thing. So if $h_2(k) $ is relatively prime to $m$, then their $gcd(h_2(k), m) = 1$. So, if $h_2(k)$ is always co-prime to each other, we can see we always get a number between $h_2(k) \bmod{m}$ that is in slots $(0, \cdots, m-1)$. If $h_2(k) $ is not relatively prime to $m$, then for the probe sequence $<h(k, 0), h(k, 1), \cdots , h(k, m - 1)>$, we might get two elements in the probe sequence that are identical to each other.

This is how I approached it, so I am not sure how that will prove that $<h(k, 0), h(k, 1), \cdots , h(k, m - 1)>$ is a permutation of $(0, 1, ... , m-1)$ anyway.

Ted Shifrin

Obviously, I recommend my own book ;) More emphasis on geometry and proofs. Seriously, what book are you using?

Avra

If you have time, please look at my question here. Thanks.

0

Q: Prove that if hash function $h_2(k)$ and $m$ are coprimes, then they produce a probe sequence that is a permutation of $(0, \cdots, ,m-1)$

Question: Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_i(k) + ih_2(k)) \bmod{m} $. Show that the probe sequence $<h(k, 0), h(k, 1), \cdots , h(k, m - 1)>$ is a permutation of the slot sequence $(0, 1, ... , m-1)$ if and only if $h_2(k)...

number-theory hash-function

Mikestylz

21:36

@TedShifrin Linear Algebra "Done Right", before reading that I proceeded by a combination of youtube videos and deriving my own proofs on paper whenever I encountered a non sequitur

Ted Shifrin

Blah. No geometry. You can also add my videos, although they intermix linear algebra and multivariable analysis.

leslie townes

Blah. Geometry.

Mikestylz

@TedShifrin I'll just try your book since I haven't taken analysis or multivariable calculus yet

leslie townes

i think axler does include one picture of a triangle in connection with orthogonal projections.

for all the good it does anybody. i dunno. :)

Mikestylz

yes chapter six has a few cute diagrams, I was looking forward to that chapter

PM 2Ring

21:41

@Avra Hint if $a + bi \equiv a + bj \pmod m$ then $b(i-j)\equiv 0 \pmod m$.

Ted Shifrin

@Mikestylz you can choose the lectures on linear algebra, but you should look at the linear algebra book, Shifrin & Adams.

Lots of pictures both in books and in videos. :)

@leslietownes smacks Leslie for good measure

Avra

@PM2Ring. So, $b$ here corresponds to $h_2(k)$ in my question please?

PM 2Ring

Yes

Avra

$i, j$ could be any value in ${0, \cdots, m-1}$ please

Mikestylz

@TedShifrin Thank you, this should help

PM 2Ring

21:46

@Avra Correct.

Ted Shifrin

We actually discuss projections a lot, and also use them as major examples of applying the change of basis formula.

Avra

@PM2Ring. If two probes hash to same slot with $h_2(k)$ that is $b$ above when we probe from $i$ to $j$ in, then this would produce a collision unless $i=j$!

@PM2Ring. Wow! Thanks

You are very fast

Not sure if I got it write though :/

*right

I am trying to say that either $b$ is a multiple of $m$ or $(i-j)$ is a multiple of $m$, but since $b$ is co-prime to $m$, then it can not be a multiple of $m$, which means it's a co-prime. $i-j$ though has to be a multiple of $m$

PM 2Ring

@Avra It only makes a collision if $(i-j)b$ is divisible by $m$. And that only happens if $i=j$, or if $b$ has a common factor with $m$ and $(i-j)$ has the other factor

Avra

@PM2Ring. Thanks. Clear. So, how then we can show that the probe sequence $<h(k, 0), h(k, 1), \cdots , h(k, m - 1)>$ is a permutation of the slot sequence $(0, 1, ... , m-1)$

PM 2Ring

And $i-j$ cannot be a multiple of $m$ unless it's $0m$ because the maximum value of $|i-j|$ is $m-1$

Avra

21:54

if we take two probes $h(k,0)$ and $h(k, 3)$ for example, they would hash to same value only if $i=j$ since $b$ is a co-prime

PM 2Ring

@Avra The pigeon-hole principle.

We have $m$ different values for $i$, and so there must be $m$ different values for $a+bi$ since there are no collisions.

So the values of $a+bi \mod m$ must be a permutation of $[0..m-1]$

Semiclassical

@PM2Ring AGM is almost designed to work for this

Integrals of pendulum are elliptic integrals after all

What I did always find cute about that , tho, is that AGM is effectively giving you a sequence of improving upper/lower bounds for the period as a function of initial angle

Avra

@PM2Ring. And if two collide, then they must be in the same slot based on pigeon-hole

So the sequence we got is a permutation of the (0,1,...,m−1)

Semiclassical

Getting pi from AGM is pretty swell too

Avra

@PM2Ring. a permutation of (0,1,...,m−1) means it could have the elements of (0,1,...,m−1) in any order please?

PM 2Ring

22:03

@Semiclassical Agreed. Traditionally, the AGM relations were used to prove useful things about elliptic integrals, but the AGM wasn't used much for calculation. That's because it uses both addition and multiolication (and square roots), which gets pretty tedious when you are doing calculations using logarithm tables. But these days, the AGM is pretty easy to do on a computer. ;)

Semiclassical

Yeah

PM 2Ring

@Avra That's right.

Avra

@PM2Ring. Thank you very much

Derivative

What do the eigenthings of the adjacency matrix of a graph tell us about the graph?

Or a source where I can read about this type of thing

Semiclassical

It does suggest an amusing way to make a calculator: use a pendulum to generate AGM values :P

Derivative

22:04

(I just read that the chromatic number of the graph is less than the greatest eigenvalue of the matrix and I'm perplexed)

Semiclassical

(I didn’t say it was a good way)

Avra

@robjohn. It was answered. Thank you too

Semiclassical

So spectral graph theory stuff?

Derivative

this is an exercise in a graph theory pdf that a study group about combinatorics sent me

PM 2Ring

@Avra No worries. You might like to read this: en.wikipedia.org/wiki/Linear_congruential_generator which is closely related to this stuff.

AMDG

22:06

@PM2Ring Well that's what I'm saying. As for your image there, it is all ones and zeroes; excluding trivial cases, everything always has at least one zero and one one, and regardless, there must be at least one occurrence of two possible strings: 10, and 01. It has to be at least NP-complete to find a pattern for which this or any permutation is optimally compressed.

Derivative

it's on the beginning of the section about chromatic numbers too, so even more perplexing

Semiclassical

Greatest eigenvslue sounds like Perron-Frobenius

AMDG

"But you can't compress everything." is what I'm claiming is not so except for a specific set of objects which are more unique than all other objects, not just by their being making it impossible that they should occupy the same space in thoughts or ideas, but properties as well.

Semiclassical

[en.m.wikipedia.org/wiki/Perron–Frobenius_theorem](link)

Ugh, I hate when wiki links break like that when I’m on mobile

Avra

@PM2Ring. Thank you. Appreciate it. Lastly, if 2 numbers $a,b$ are co-primes, then $a \bmod{b} \ne 0$

AMDG

22:11

What one would ultimately have to prove for it to be so that all things which do not fall into the set of most-unique objects is that for all transformative operations applied to a set which do not change the number of elements and which operations are invertible, that there does not exist a set of operations which leads all elements to be completely homogeneous in some way.

PM 2Ring

@Avra Correct

Avra

@PM2Ring. Thank you. 100% clear

PM 2Ring

@AMDG If your compressor can say "I refuse to compress that data because it's not sufficiently interesting", then sure, it's output files can always be smaller than its input files. But if it's a general compressor, it's not permitted to do that.

AMDG

I'm not quite sure what that means. I am speaking of "compressors" in general.

And define interesting because most-unique objects are incredibly more interesting by the very fact that they contain features which no other object can have and cannot be replicated.

PM 2Ring

Please see en.wikipedia.org/wiki/Lossless_data_compression#Limitations

AMDG

22:21

Something provably incompressible by any possible algorithm in the set of compression algorithms must be in the set of most-unique objects. The moment a copy of a most-unique object is present, the whole is no longer unique and can be compressed.

Semiclassical

The back of my brain says think about entropy but I’m also tired enough that this may be nonsense

Ted Shifrin

I prefer Gibbs free energy and enthalpy.

Semiclassical

Something along the lines of a compression algorithm always increasing Shannon entropy over the set of all possible files

In which case you hope most of your files land in a subset whose entropy happens to be lower

AMDG

I have already considered entropy here. Entropy, randomness, whatsoever you choose, is capable of producing redundancy. I would note that it is impossible, however, to generate via algorithm true entropy because even for lossy operations such as XOR can have multiple inputs that produce the same correct result, and we do not require that we have the original inputs, just inputs that produce a correct result.

The only difference is that entropy is only probabilistically redundant whereas algorithms guarantee redundancy because the algorithm itself exists so long as it has no basis in entropy or non-determinism.

PM 2Ring

2 hours ago, by copper.hat

i think of the pigeon hole principle as a ceiling on an average :-)

AMDG

22:35

One last note: I'm not sure that this necessarily counts as sophistry, but having thought about it, I believe it fair to classify purported algorithms which have themselves as the result are in fact state and not behavior and therefore not algorithms if we define state to be anything that is constant, and constancy defined as having the same value without beginning or end.

copper.hat

what are you smoking?

AMDG

@copper.hat Have you never heard of philosophy, that thing that considers the substances of things that we perceive, whether material or immaterial, which is so pervasive that it is implicated in all fields as fundamental to every field?

dc3rd

sticky icky icky possibly Copper :p

AMDG

I have not studied philosophy formally. It is merely sufficient that one think about or reason about something at all to be acting like a philosopher.

Anyways, my purpose in pointing this out is that one could not claim that a program which produces itself upon execution is deterministic but incompressible as an algorithm, and that it is more fitting that said program not be considered a program at all, but that it is state for which the fact that it exists through behavior is accidental because it cannot be distinguished from state. It would instead be state and part of the set of most-unique objects.

PM 2Ring

Here's a concrete example. We want to compress all possible bitstrings of length 16. There are $2^{16}=65,536$ such strings. Any compression scheme must result in the compressed versions having an average length of at least 16. Otherwise, we have a way of indexing all possible 16 bit numbers in under 16 bits, in defiance of the pigeon-hole principle.

Think of the compressed version as an index into the set of all 16 bit strings. We need to have at least 65,536 different indices, or we get collisions. And we need at least 16 bits (on average) to get that many indices.

copper.hat

22:43

:-)

AMDG

What exactly does index here mean, and what do you mean by "under 16 bits"?

copper.hat

sounds like information theory to me... time for a swim in the shannon

PM 2Ring

@AMDG Like an array index. When you give the decompressor the compressed bitstring it has to return the original uncompressed version.

AMDG

Why not just call them compressed strings, uncompressed strings, or why not just make a new word for referring to these more compactly?

Well anyways

PM 2Ring

I'm trying to present the same information to you in various ways in the hope that it will finally click.

AMDG

22:52

One can only learn by building on what he already knows. If you want to teach me something, then you need to know what I already know.

PM 2Ring

"Under 16 bits" means 15 bits or fewer. ;)

AMDG

Under 16 bits in compressed representation, or something else?

And if compressed representation, a whole array of 2^16 bitstrings or what?

You said we want to compress all possible bitstrings of length 16. Cool, well then all I need to do is record the order of the elements and increment a counter to reproduce each value. If you're saying that each individual record of the position of each element is the index, and that is what must be under 16 bits in size, then I understand, and I would note that you can use a sort of float to represent some of the integers in this range with far less than 16 bits, esp. if they're powers of two.

You can also just remove trailing zeroes or ones, and you can halve the number of values to be compressed that you need to worry about by understanding that you can NOT the values.

PM 2Ring

You need to make the average length of a compressed string <16.

AMDG

Average assuming all 2^16 values including any supposed outliers?

Finally, a challenge I can enjoy with practical consequences.

Clearly, instead of school, I should have been skipping and coming to this chatroom.

PM 2Ring

I don't know what you mean by outliers here. There are 2^16 different possible inputs to the compressor. It has to produce a compressed version for each one.

Now the compressed version doesn't always have to be shorter than 16 bits, but it's desirable that it's not longer, and the mean length of the entire collection of compressed versions must not be greater than 16.

AMDG

23:08

Ah, ok, I see. I was thinking in my mind that we were restricted to 16 bits or less, but that's how I would have approached this anyways, so that's what I would do.

Unfortunately, I am not at the stage where I need to implement lossless compression algorithms for my standard library, so I will not be exerting my intellect on this exercise for the time being when I have more important things that I need to allocate my time for thinking for. I had to work on fundamental algorithms as the only setback to go forward with my project, at least in my mind, and these other things came up as little curiosities. Pleasant conversation, though.

Transcript for

$Mathematics$ Mathematics