4
$\begingroup$

Given $n\in\mathbb{N}$, and $f:\mathbb{N}^*\rightarrow \mathbb{N}$, let define $Pos$ as:

$$Pos(f)(n)= |\{x \leq n, f(x)=f(n)\}|$$

When given $n\in\mathbb{N}$, this function gives the 'position' of $n$ in the list of the elements of $f^{-1}(f(n))$.

Therefore, $f$ injective $\Leftrightarrow Pos(f)=1_{\mathbb{N}}$,

and $f$ constant $\Leftrightarrow Pos(f)=Id$

One can show that $Pos(Pos(Pos(f))=Pos(f)$ for all $f\in\mathcal{F}(\mathbb{N}^*,\mathbb{N})$, and hence that $Pos\circ Pos$ is the identity on $Pos(\mathcal{F}(\mathbb{N}^*,\mathbb{N}))$

We obviously can define $Pos$ on smaller spaces, such as $\mathcal{F}([1,n],\mathbb{N})$.

We call a $Pos$ function an object in the image of $Pos$, and call $\mathbb{P}os(\mathbb{N}^*)$ the considered functions.

Let $f$ be in $\mathcal{F}(\mathbb{N}^*,\mathbb{N})$, then we have $$f\in\mathbb{P}os(\mathbb{N}^*)\Leftrightarrow Pos(Pos(f))=f$$.

One can show that there is exactly as much $Pos$ functions defined over $[1,n]$ as Young Tableau of $n$ cells.

Let be $n\in\mathbb{N}$ and $(X_k)_{k\in[1,n]}$ a family of independant uniform random variables over $[1,n]$.

Let $f_n\in\mathcal{F}([1,n],\mathbb{N})$ verifying $f_n(k)=X_k(\omega)$ for some $\omega\in\Omega$ and for all $k\in[1,n]$.

Then (Conjecture):

$Pos(Pos(f_n))\rightarrow_{n\rightarrow +\infty} g_{|\mathbb{N}}$ where $g$ is some function in $\mathcal{C}^\infty(\mathbb{R}^+,\mathbb{R})$

4 Realisation of $f_{1000}$: (https://cloud.sagemath.com/blobs//projects/19785c4f-3835-4790-b566-c9bb43c2c63c/.sage/temp/compute1-us/22034/tmp_wURmVN.svg?uuid=8af1e4c5-1c5f-48af-b1ea-67937f2e68a9)

enter image description here

4 realisations of $Pos(Pos(f_{1000}))$, where the black line is the identity, and the $g$ function would be the mean of all the upper functions: (https://cloud.sagemath.com/blobs//projects/19785c4f-3835-4790-b566-c9bb43c2c63c/.sage/temp/compute1-us/22034/tmp_ZH6Nhx.svg?uuid=1b3005a6-114a-4b94-a1a3-05d788e95101)

enter image description here

More precision up to 10 000

!(https://cloud.sagemath.com/blobs//projects/19785c4f-3835-4790-b566-c9bb43c2c63c/.sage/temp/compute1-us/20433/tmp_X0M9WX.svg?uuid=8b2d6516-0581-459d-893d-63616dab2434)

enter image description here

Do you have ideas to prove or disprove such a result? Do you recognize some of the functions generated this way or do you have some intuition on it?

One of my ideas was to look at the random function $Z(n)$, being the upper bound of $Pos(Pos(f_n))$. Interestingly, $Z$ seems to be homotethic, with ratio surprisingly close to $\frac{2}{pi}$.

The graph of $Z(n)$ for $n\in[1,1000]$ in blue, and $x\mapsto \frac{2x}{pi}$ in red: (https://cloud.sagemath.com/blobs//projects/19785c4f-3835-4790-b566-c9bb43c2c63c/.sage/temp/compute1-us/25054/tmp_n0iiY_.svg?uuid=7c935133-8773-4523-9a89-fda1b4b746b5)

enter image description here

I'm aware it's a very specific result in a field that isn't very documented, but, i'd be really glad to know if anyone had ideas to keep on studying this $Pos$ function.

I'm sorry that the images cannot be shown directly on the site, because i just signed in, and therefore have not any reputation points. Same for the first link, i'm limited to 2 so i let the most important. It's one of the theory i'm working on and i thought you might be helping.

$\endgroup$
  • 1
    $\begingroup$ What's $\mathbb{N}^\ast$? $\endgroup$ – Todd Trimble Apr 14 '16 at 11:44
  • 1
    $\begingroup$ it's a french notation that mean $\mathbb{N}$ without $0$. It's used for the property $f $constant$ \Leftrightarrow Pos(f)=Id$ which would be $f$ constant$ \Leftrightarrow Pos(f)=Id+1$ if the origin space was $\mathbb{N}$. $\endgroup$ – Arpad Deak-Chevillard Apr 14 '16 at 12:59
  • $\begingroup$ Which type of convergence do you mean? If it is "pointwise", then, as $n\to\infty$, the first $k$ terms of $X_1(\omega)$, $X_2(\omega)$, $\dots $ are whp disinct for any fixed $k$, so $Pos(Pos(f_n))|{[1,k]}$ whp coincides with $\mathord{id}_{[1,k]}$. I assume you mean something different? $\endgroup$ – Ilya Bogdanov Apr 15 '16 at 14:25
  • $\begingroup$ In my opinion, the convergence would be kind of "almost sure". $\endgroup$ – Arpad Deak-Chevillard Apr 16 '16 at 10:52
  • $\begingroup$ Consider the $k$ variables $X_1,..,X_k$ uniform over $[1,k]$. Although, two of the variables ($\frac{n-1}{n})$, the probability that they all are different tends to $0$ as $n\rightarrow\infty$, because having the 1st different from all the former is easy (100%), $\frac{1}{k-1}$, having 3rd different from the 1st two is $1/2(\frac{1}{k-1}+\frac{1}{k-2})$, and so on. The function $Z$ exactly estimates how much of the $k$ Variables are distincts, because it's the condition that make $Pos(Pos)$ grow. $\endgroup$ – Arpad Deak-Chevillard Apr 16 '16 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.