Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics comma complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration finite foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorKeithEPeterson
    • CommentTimeMar 1st 2017
    • (edited Mar 1st 2017)

    Is there a way that makes finding inverses a bit easier?

    I defined a really nice pairing function based on a space filling curve which acts on natural numbers,

    x,y={(xy)(x0mod2) x 2+xy (xy)(x1mod2) x 2+y (y>x)(y0mod2) y 2+y+x+1 (y>x)(y1mod2) (y+1) 2y+x \left \langle x,y \right \rangle = \left \lbrace \begin{matrix} (x \geq y) \wedge (x \equiv 0 \mod 2) & x^2 + x - y \\ (x \geq y) \wedge (x \equiv 1 \mod 2) & x^2 + y \\ (y \gt x) \wedge (y \equiv 0 \mod 2) & y^2 + y + x + 1 \\ (y \gt x) \wedge (y \equiv 1 \mod 2) & (y+1)^2 - y + x \end{matrix} \right. ,

    and would like to find it’s projections. Is such a thing possible?

    • CommentRowNumber2.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 1st 2017
    • (edited Mar 1st 2017)

    This seems to work, i.e., gives a bijection ,:×\langle -, - \rangle: \mathbb{N} \times \mathbb{N} \to \mathbb{N}, although it’s a tad unusual. (I wouldn’t call it a “space-filling curve” though; in usual parlance, a space-filling curve is a continuous surjection with domain the unit interval II, e.g., II 2I \twoheadrightarrow I^2.) Also, it’s much more common to use a simpler-looking one-line formula such as

    (x,y)(x+y+12)+y(x, y) \mapsto \binom{x + y + 1}{2} + y

    But anyway, if n=x,yn = \langle x, y \rangle labels the grid point (x,y)(x, y), and if FlFl denotes the floor function, then putting f=Fl(n)f = Fl(\sqrt{n}) we have

    (x,y)=(f,nf 2) if f 2nf 2+fandfisodd (x,y)=(f,f 2+fn) if f 2nf 2+fandfiseven (x,y)=(nf 2f1,f) if f 2+f+1nf 2+2f\array{ (x, y) = (f, n - f^2) & if & f^2 \leq n \leq f^2 + f\; and\; f\; is\; odd \\ (x, y) = (f, f^2 + f - n) & if & f^2 \leq n \leq f^2 + f\; and\; f\; is\; even \\ (x, y) = (n - f^2 - f - 1, f) & if & f^2 + f + 1 \leq n \leq f^2 + 2f }

    assuming my calculations are correct (which I won’t swear to).

    Oh, by the way, notice that y 2+y+x+1=(y+1) 2y+xy^2 + y + x + 1 = (y + 1)^2 - y + x, so your third and fourth lines could have been combined into a single line.

    • CommentRowNumber3.
    • CommentAuthorKeithEPeterson
    • CommentTimeMar 2nd 2017
    • (edited Mar 2nd 2017)

    Thank you, Todd.

    Actually, here’s an even better function I figured out that’s based on the curve I wanted that I was trying to define last night:

    x,y={(x0mod2)(xy) x 2+y (y0mod2)(y>x) (y+1) 2(x+1) (x1mod2)(x>y) (x+1) 2(y+1) (y1mod2)(yx) y 2+x \langle x, y \rangle = \left\{\begin{matrix} (x \equiv 0 \mod 2) \wedge (x \geqslant y) & x^2 + y \\ (y \equiv 0 \mod 2) \wedge (y \gt x) & (y+1)^2 - (x+1)\\ (x \equiv 1 \mod 2) \wedge (x \gt y) & (x+1)^2 - (y+1)\\ (y \equiv 1 \mod 2) \wedge (y \geqslant x) & y^2 + x \\ \end{matrix}\right.

    I could see it being a mechanical way to iterate an infinite matrix, so having the projections has an actual real world use.

    Edit: I made it from chopping in half, then flipping the pairing function:

    {(xy) x 2+y (y>x) (y+1) 2(x+1) \left\{\begin{matrix} (x \geqslant y) & x^2 + y \\ (y \gt x) & (y+1)^2 - (x+1)\\ \end{matrix}\right.
    • CommentRowNumber4.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 2nd 2017

    Again, it should not be called a “space-filling curve”.

    I’m mildly curious why this choice of bijection in 3., with the bifurcation into odd and even cases. A cousin to the bijection of 1. is the two-line expression

    x,y=x 2+y if xy x,y=y 2+y+x+1 if x<y\array{ \langle x, y \rangle = x^2 + y & if & x \geq y \\ \langle x, y \rangle = y^2 + y + x + 1 & if & x \lt y }

    which to me looks simpler, and is closely connected with a standard well-ordering on ×\mathbb{N} \times \mathbb{N} where (x,y)<(x,y)(x, y) \lt (x', y') if either max{x,y}<max{x,y}\max\{x, y\} \lt \max\{x',y'\} or max{x,y}=max{x,y}y<y\max\{x, y\} = \max\{x',y'\} \wedge y \lt y' or max{x,y}=max{x,y}y=yx<x\max\{x,y\} = \max\{x', y'\} \wedge y = y' \wedge x \lt x'. (A similar type of well-ordering arises in one of the standard proofs that κ 2=κ\kappa^2 = \kappa for infinite cardinals κ\kappa, assuming the axiom of choice.)

    • CommentRowNumber5.
    • CommentAuthorKeithEPeterson
    • CommentTimeMar 2nd 2017
    • (edited Mar 2nd 2017)

    That I can answer quite easily, The reason for splitting the terms into odd and even case can be seen from the tables:

    Compare the image of,

    {(xy) x 2+y (y>x) (y+1) 2(x+1) \left\{\begin{matrix} (x \geqslant y) & x^2 + y \\ (y \gt x) & (y+1)^2 - (x+1)\\ \end{matrix}\right.

    Image: http://imgur.com/KsskDoQ

    with that of,

    x,y={(x0mod2)(xy) x 2+y (y0mod2)(y>x) (y+1) 2(x+1) (x1mod2)(x>y) (x+1) 2(y+1) (y1mod2)(yx) y 2+x \langle x, y \rangle = \left\{\begin{matrix} (x \equiv 0 \mod 2) \wedge (x \geqslant y) & x^2 + y \\ (y \equiv 0 \mod 2) \wedge (y \gt x) & (y+1)^2 - (x+1)\\ (x \equiv 1 \mod 2) \wedge (x \gt y) & (x+1)^2 - (y+1)\\ (y \equiv 1 \mod 2) \wedge (y \geqslant x) & y^2 + x \\ \end{matrix}\right.

    Image: http://imgur.com/NIok3JM

    Also, from Cantor’s pairng function,

    (x+y)(x+y+1)2+y\frac{(x+y)(x+y+1)}{2}+y

    Image: http://imgur.com/Nh25uoj

    I found the derivation,

    {(x+y)0mod2 (x+y)(x+y+1)2+y (x+y)1mod2 (x+y)(x+y+1)2+x \left\{\begin{matrix} (x+y)\equiv 0 \mod 2 & \frac{(x+y)(x+y+1)}{2}+y\\ (x+y)\equiv 1 \mod 2 & \frac{(x+y)(x+y+1)}{2}+x\\ \end{matrix}\right.

    Image: http://imgur.com/CXmfFAE

    Splitting up the functions this way allows for “ox-plowing” variants.

    I was motivated by the page http://mathworld.wolfram.com/PairingFunction.html, which pointed out that the two ox-plowing functions given by Stein in his book had no explicit formula. Well, now they do.

    As a bonus, here’s the pairing function I first defined,

    {(xy)(x0mod2) x 2+xy (xy)(x1mod2) x 2+y (y>x) (y+1) 2y+x\left\{\begin{matrix} (x \geq y) \wedge (x \equiv 0 \mod 2) & x^2 + x - y \\ (x \geq y) \wedge (x \equiv 1 \mod 2) & x^2 + y \\ (y \gt x) & (y+1)^2 - y + x \end{matrix} \right.

    Image: http://imgur.com/as34fVe

    • CommentRowNumber6.
    • CommentAuthorDavidRoberts
    • CommentTimeMar 3rd 2017

    While this is nice to think about, is there are reason why the question was asked here rather than, for example, math.stackexchange?