@joshuagrochow@mathstodon.xyz avatar

joshuagrochow

@joshuagrochow@mathstodon.xyz

Assoc. Professor @ CU Boulder Comp. Sci. & Math; Research interests: theoretical computer science, pure mathematics, and complex systems.
Other interests: climate change; accurate (long)COVID info; equity, inclusion, & accessibility; improving academia. #BlackLivesMatter #TransRightsAreHumanRights #LandBack #CovidIsAirborne #CleanTheAir #StillMasking #MaskUp #TCS #TheoryCS #math #ComplexSystems #complexity (both kinds) #academia

This profile is from a federated server and may be incomplete. Browse more on the original instance.

stux, to bsky
@stux@mstdn.social avatar

Im so glad doesn’t need my full date of birth!

Oh wait..

I’m sure it’s just for a ‘happy birthday’ right! :no: 🙅 :bugcat_nod:

Thanks but no thanks

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@stux @the_skotts I don't see custom feeds in the roadmap you linked to. Did I just miss it?

joshuagrochow, to random
@joshuagrochow@mathstodon.xyz avatar

Rogers's Equivalence Theorem (https://en.wikipedia.org/wiki/Admissible_numbering#Rogers'_equivalence_theorem) is more amazing than it sounds.

(Plus a question about it at the end)

It says that any two admissible numberings (aka programming languages: https://en.wikipedia.org/wiki/Numbering_(computability_theory)) of the partial computable functions are computably isomorphic.

To see how amazing this is: it's standard that you can write a program to compile Python programs to Java programs and vice versa. Just from those two compilers, Rogers's Equivalence Thm implies that there is a total computable function f that transforms Java programs into input-output-equivalent Python programs that is 1-to-1 (not so surprising) and onto - every Python program arises as f(p) for some Java program p, and p and f(p) compute the same function. That is pretty surprising!

#computability #programming #logic

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

Now the Q: Shouldn't there be some analagous theorem for Gödel numberings? Sure, they're not unique (https://en.wikipedia.org/wiki/G%C3%B6del_numbering#Lack_of_uniqueness), but isn't there a sense in which "all reasonable Gödel numberings are isomorphic"?

#logic #math

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@andrejbauer Why not? Your conclusion follows already from the existence of compilers between the two languages and Turing-completeness. But Rogers's Theorem actually gives a bijection between the two sets of indices (programs).

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@andrejbauer I don't fully understand yet about the general category-theoretic setting in your other post (though I hope to!). But in the setting of Rogers's Theorem, it very explicitly provides a bijection h:ℕ→ℕ such that φₑ=ψₕ₍ₑ₎ for all e, where here the natural numbers are being used as the codes of the programs. So it is literally providing a bijection between the sets of programs.

Here is the precise statement from Soare's book:

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@andrejbauer Oh sorry it is his newer one: https://doi.org/10.1007/978-3-642-31933-4. (He still essentially relegates the proof to several exercises, but gives more of an outline of how it should go.)

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@andrejbauer Ah, interesting! I was not aware that Rogers's original version didn't have this bijection as part of it. I have learned both some history and some math from you today - thanks!

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@11011110 Indeed! One part of the proof (Exercise 1.7.7 in Soare's Turing Computability book) uses a slight generalization of the Myhill Isomorphism Thm, which is essentially the same as Cantor-Schroeder-Bernstein, which is essentially the same as Berman & Hartmanis's proof in the case that the reductions in both directions are 1-1 and length-increasing.

joshuagrochow, to science
@joshuagrochow@mathstodon.xyz avatar

I continue to be disappointed by a scientific community that requires people to unnecessarily uproot their lives to be a part of it.

#science #academia

ProfKinyon, to random
@ProfKinyon@mathstodon.xyz avatar

It never ceases to amaze me how a document with finitely many words of finite length constructed from a finite alphabet can have uncountably many typos.

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ProfKinyon Konig's Lemma?

joshuagrochow, (edited ) to random
@joshuagrochow@mathstodon.xyz avatar

The Hoffman-Singleton graph can apparently be constructed as the Cayley graph of a magma: https://en.wikipedia.org/wiki/Hoffman%E2%80%93Singleton_graph#Construction_on_a_groupoid/magma

It:

  • isn't a quasigroup
  • has a 2-sided identity (0,0,0)
  • isn't associatve
  • isn't commutative

What is this magma?? Anyone have any ideas?

I think when the first coordinate is zero, the corresponding 25 elements are a copy of the cyclic group of order 25 (generated by (0,1,1)).

#algebra #graph

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@jix Generally looks right to me. Nice!

However, since the operation isn't commutative, did you try a version where (on line 33 of your code) you do magma_op(g,v) instead of (v,g)? (I'm just trying to think of other potential typo-style quick fixes that might work. If we can't get it to work, I think maybe we should contact the authors to see what's up, but good to give it our best shot first. When I have some time I can try to reproduce independently as well.)

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@jix @ProfKinyon Ah, very nice! Did you also update your code and get that to verify? (Not that you have to do that, just curious. I didn't see it updated on github, but maybe you did it privately.)

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@jix @ProfKinyon Great! With this updated formula, in terms of the algebraic structure, we now have that triples of the form (0,x,y) form a subgroup isomorphic to C_5 x C_5. Call that subgroup H. Then the whole magma is H union (1,0,0)*H. So it's some sort of magma-y index-2 extension of the group C_5 x C_5.

The submagma (,0,) is almost the dihedral group of order 10 (it would be if the 2^a were instead (-1)^a). It sort of makes sense that it's not because there are these Petersen subgraphs, and the Petersen graph is similar but not the same as the Cayley graph of the dihedral group. (In fact, I'd bet the Cayley graph of the submagma (,0,) gives the Petersen graph.)

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ProfKinyon @jix Right! That submagma is not a group, but it's very "group-like", just as the Petersen graph is "almost the Cayley graph of the dihedral group". (Is it a loop?)

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ProfKinyon @jix Okay, I couldn't wait, so I did a little check. It is indeed a loop.

Left inverse=right inverse, namely (x,0,z)^{-1}=(-x, 0, -2^{-x}z). Though I have not yet checked if it has the inverse property.

A little code tells me it is not Moufang, but I don't know if I trust that, since I don't really understand Moufang, I'm just copying definitions.

I'm on the edge of my seat (just for curiosity though, it's not like URGENT) to know if this is some familiar loop. It is certainly nice!

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ProfKinyon @jix Ah yes, I was indeed making exactly that mistake. Thanks!

Also, cool. When I get a chance I want to verify that its Cayley graph is indeed the Petersen graph as I suspect. (Which would raise the question: are all vertex-transitive undirected graphs the undirected Cayley graph of some magma with special properties?? I know they are all Cayley-Schreier coset graphs of some group/subgroup pair.)

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ProfKinyon @jix Yeah e.g. it strikes me as an interesting question to classify the loops that have an undirected Cayley graph = Petersen or =Hoffman-Singleton.

Anyone know what the next smallest vertex-transitive graph is after Petersen that is not the Cayley graph of a group?

joshuagrochow, (edited )
@joshuagrochow@mathstodon.xyz avatar

@ProfKinyon @jix I found a few papers that seem to mostly answer these kinds of questions:

https://doi.org/10.1016/j.disc.2008.05.027

https://arxiv.org/abs/2007.06432

https://arxiv.org/abs/1803.08518
https://arxiv.org/abs/1903.06521

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ProfKinyon @jix If a quasigroup has a Cayley graph that is also the Cayley graph of a group, I would expect that to put strong structural restrictions on the quasigroup. Right? (If so: what are they? Can we characterize such quasigroups?)

For formulas: there's also something funny because the underlying coordinates don't have the same domain (e.g. in the one we were looking at a mod 2, b and c mod 5), but they're all finite. If we view those just as integers from a bounded range, then you can rewrite 2^a as the polynomial (1+a), which agrees with 2^a for a in {0,1}.

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ProfKinyon @jix Can a 1-generated quasigroup have a quasiCayley graph (I guess they're called) that is a cycle, if it's not the cyclic group? Or does it's quasiCayley graph have to be a path?

joshuagrochow, to random
@joshuagrochow@mathstodon.xyz avatar

I posted a brief note about Hensel lifting for systems of polynomial equations when number of eqns ≠ number of vars.

Purely expository b/c I couldn't find it anywhere, even though it's elementary. Feedback appreciated before I decide about posting on arXiv!

https://home.cs.colorado.edu/~jgrochow/hensel-notes.pdf

#AlgebraicGeometry #algebra

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ducasleo Yes to your conclusion! But I think doubling the exponent of p already corresponds precisely to the quadratic convergence in Newton's method.

In Newton's method, if the error at one step is eps, the error at the next step is proportional to eps^2 (if it's a simple root), hence the number of digits of accuracy doubles. Similarly, in Hensel lifting, the p-adic norm gets quadratically smaller, or equivalently, the number of p-adic digits doubles each iteraction.

joshuagrochow,
@joshuagrochow@mathstodon.xyz avatar

@ducasleo we've all been there lol. (Well, at least those of us that are parents.)

joshuagrochow, to random
@joshuagrochow@mathstodon.xyz avatar

The more I learn about quasigroups, the more I think they deserve the name in a way that semigroups don't.

Semigroups that faithfully embed into a group maybe are ok b/c they're "half the group" (e.g. positive reals inside the reals, under addition).

But not general semigroups. They need a new name.

#algebra #quasigroup #semigroup

  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • JUstTest
  • ngwrru68w68
  • everett
  • InstantRegret
  • magazineikmin
  • thenastyranch
  • rosin
  • GTA5RPClips
  • Durango
  • Youngstown
  • slotface
  • khanakhh
  • kavyap
  • DreamBathrooms
  • provamag3
  • tacticalgear
  • osvaldo12
  • tester
  • cubers
  • cisconetworking
  • mdbf
  • ethstaker
  • modclub
  • Leos
  • anitta
  • normalnudes
  • megavids
  • lostlight
  • All magazines
    •