## Proving injectivity for an algorithm computing a function between sets of different types of partitions [closed]

I am attempting to solve the following problem:

Let $$A$$ be the set of partitions of $$n$$ with elements $$(a_1, \dots, a_s)$$ such that $$a_i > a_{i+1}+a_{i+2}$$ for all $$i < s,$$ taking $$a_{s+1} = 0.$$ Define $$g_n = F_{n+2}-1$$ and let $$B$$ be the set of partitions of $$n$$ as $$b_1 \ge \dots \ge b_s$$ such that $$b_i \in \{g_n\}$$ for all $$i,$$ and if $$b_1 = g_k$$ for some $$k,$$ then $$g_1, \dots, g_k$$ all appear as some $$b_i.$$ Prove $$|A|=|B|.$$

Attempt: Let $$e_i$$ be the vector with $$1$$ at position $$i$$ and $$0$$ elsewhere. If $$b_1 = g_k,$$ let $$c=(c_k, \dots, c_1)$$ count how many times $$g_i$$ appears. We calculate $$f: B \to A$$ as follows:

Let $$c=(c_k,\dots,c_1), a=(0,\dots,0).$$ While $$c \ne 0,$$ let $$d_1 > \dots > d_k$$ be the indices such that $$c_{d_i} \ne 0.$$ Replace $$c, a$$ with $$c-(e_{d_1}+\dots+e_{d_k}), a+(g_{d_1} e_1 + \dots + g_{d_k} e_k)$$ respectively. After the while loop ends, let $$f(b)=a.$$

Let $$\sum a, \sum b, \sum c$$ be the sum of the components of $$a, b, c$$ respectively. Since $$\sum c$$ decreases after every loop, the algorithm terminates and $$f(b)$$ is well-defined. Since $$c_k g_k + \dots + c_1 g_1 + \sum a$$ does not change after every iteration, is $$\sum b$$ at the start and $$\sum a$$ at the end, we have $$\sum f(b) = \sum b = n,$$ so $$f(b)$$ is also a partition of $$n.$$ Now $$a = (g_k, \dots, g_1)$$ after the first loop, which satisfies the condition $$g_i > g_{i-1}+g_{i-2}$$ since $$g_i = F_{n+2}-1 = (F_{n+1}-1)+(F_n-1)+1 > g_{i-1}+g_{i-2}.$$ Furthermore, after every iteration of the loop, the difference $$a_i – (a_{i-1}+a_{i-2})$$ changes by $$0, g_{d_j}-g_{d_{j-1}} > 0,$$ or $$g_{d_j}-(g_{d_{j-1}}+g_{d_{j-2}}) > 0,$$ so we have $$a_i > a_{i-1} + a_{i-2}$$ at the end and hence $$f(b) \in A.$$ Thus, $$f: B \to A$$ is well-defined.

In order to prove the injectivity of $$f,$$ it suffices to prove each loop iteration as a mapping $$(c,a) \to (c’,a’)$$ is injective, which would imply the mapping $$(c,0) \to (0,a)$$ that the while loop creates is injective. Indeed, if $$f(b_1) = f(b_2) = a$$ with $$(c_1, 0), (c_2, 0)$$ being sent to $$(0, f(b_1)) = (0,a), (0, f(b_2)) = (0,a)$$ respectively, then we have $$(c_1, 0) = (c_2, 0) \Rightarrow c_1 = c_2 \Rightarrow b_1 = b_2.$$

Suppose $$d_1 > \dots > d_i, f_1 > \dots > f_j$$ are the non-zero indices of $$c_1, c_2$$ respectively and $$c_1 – (e_{d_1}+\dots+e_{d_i}) = c_2 – (e_{f_1}+\dots+e_{f_j}), a_1+g_{d_1}e_1 + \dots+ g_{d_i} e_i = a_2 + g_{f_1} e_1 + \dots + g_{f_j} e_j.$$ If $$x \ge 2$$ is an entry of $$c_1,$$ it decreases by $$1,$$ so the corresponding entry in $$c_2$$ after $$c_2$$ is modified is also $$x-1,$$ which means it must’ve been $$(x-1)+1 = x$$ before since $$x-1>0.$$ Thus, if the values of two positions of $$c_1, c_2$$ differ, one is $$1$$ and the other is $$0.$$ However, if $$c_1 = (1,0), a_1 = (3,1), c_2 = (0,1), a_2 = (4,1),$$ then $$(a_1, c_1), (a_2, c_2)$$ both get sent to $$((5,1), (0,0)).$$ I can rule out this specific example by arguing that one of the pairs is illegal and could not have come from any choice of initial $$c,$$ but I have no idea on how to do this in general.

What should I do next in order to show $$f$$ is injective? Furthermore, since the problem I’m trying to prove is correct, injectivity would imply $$f$$ is secretly a bijection. But I have no clue on how to even start on the surjectivity of $$f,$$ so I just constructed a similar algorithm for $$g: A \to B$$ in the hopes of proving $$g$$ is injective too. If I can show $$f$$ is injective I will probably know how to show $$g$$ is.

Here is an example of $$f, g$$ in practice:

Let $$n = 41, b = (12, 7, 7, 4, 4, 2, 2, 2, 1) \Rightarrow c = (1, 2, 2, 3, 1).$$

$$((1, 2, 2, 3, 1), (0,0,0,0,0)) \to ((0, 1, 1, 2, 0), (12, 7, 4, 2, 1)) \to ((0, 0, 0, 1, 0), (19,11,6,2,1)) \to ((21,11,6,2,1),(0,0,0,0,0)),$$ so $$f(b) = (21,11,6,2,1).$$

Let $$a = (21, 11, 6, 2, 1).$$

$$((21,11,6,2,1),(0,0,0,0,0)) \to ((9,4,2,0,0), (1,1,1,1,1)) \to ((2,0,0,0,0),(1,2,2,2,1)) \to ((0,0,0,0,0),(1,2,2,3,1)),$$ so $$g(a) = (12, 7, 7, 4, 4, 2, 2, 2, 1).$$

## Injectivity not required for unification algorithms?

When learning about a general unification algorithm, we learned the rule decompose, which states unifying $$G \cup \{f(a_0,…a_k)=f(b_0,…,b_k)\} \Rightarrow G \cup \{a_0=b_0,…a_k=b_k\}$$. The question of, “What if $$f$$ is not injective?” stood out to me. Say $$f$$ is not injective, and we traverse that branch of computation where $$f(a_0,…a_k)=f(b_0,…,b_k) \Rightarrow \{a_0=b_0,…,a_k=b_k\}$$ and lead to failure. Is it possible that there’s another way to assign $$a_0,…,a_k$$ to $$b_0,…b_k$$ such that it’s unifiable?

I was thinking maybe of an example to demonstrate what I mean. This may not be a good example, but say we consider $$f(x,y) = x+y$$, and we want to unify $$f(h(a),g(b)) = f(g(c),h(d))$$ then we would fail by assigning $$\{h(a) = g(c), g(b)=h(d)\}$$ by decompose, but succeed in unification if instead we first switch the arguments of $$f$$ (valid since $$f(a,b)=f(b,a)$$), which will yield $$\{a \mapsto d, b \mapsto c\}$$.

I was reading a bit about it in this paper on page 6 where they discuss the idea of strictness in terms of decompose, but I don’t quite understand it, and more generally how we can perform this unification step of decompose on a general $$f$$ without somehow backtracking on failure.

## Injectivity verification in o(n) space and O(n) time

The problem I want to solve is this: Given a list $$A$$ of $$n$$ elements, I want to verify that they are all distinct. If I were to do this “myself”, I would need $$O(n)$$ space and $$O(n\log n)$$ time to solve it, e.g. via a hashmap or binary tree. Luckily, I have an untrustworthy but omnipotent oracle ally who is willing to give me hints on how to solve the problem.

The oracle is allowed to provide me $$O(n)$$ of hints, and I want an algorithm that will read $$A$$ and the oracle input (both read only) and determine either that $$A$$ has no duplicates, or that the oracle has given me a bad hint, in time $$O(n)$$ and much smaller read-write space ($$O(1)$$ or $$O(\log n)$$).

Can it be done?

## Is the injectivity radius (semi) continuous on a non-complete Riemannian manifolds?

Let $$\mathcal{M}$$ be a Riemannian manifold, and let $$\mathrm{inj} \colon \cal M \to (0, \infty]$$ be its injectivity radius function.

It is known that if $$\cal M$$ is connected and complete, then $$\mathrm{inj}$$ is a continuous function: see for example [Lee, Introduction to Riemannian Manifolds, 2018, Prop. 10.37].

What is known in the case where $$\cal M$$ is not complete? Is $$\mathrm{inj}$$ also continuous? If not, is there a known counter-example? Would $$\mathrm{inj}$$ still be semi-continuous?

This question is similar to the question “The continuity of Injectivity radius”, but the discussion there focuses on compact or complete manifolds.

## A stronger notion of injectivity

An injective map between two sets of same cardinality at least one of whom is finite is bijective. This not true if we drop the assumption that at least one of the sets is finite. Is there a strengthening of the notion of injectivity such that the statement continues to hodl?

## WIth pushout each orthogonality class is an injectivity class

I cannot see how follows the equality $$\cal M^{\bot}=M^*$$-Inj below: (both inclusions are wanted)

## Injectivity radius on complete manifolds with postive and bounded curvature

I have two question:

1) Are there any examples of complete manifold with strictly postive and bounded section curvature which has zero injective radius?

2) Is there a sequence of non-compact complete manifolds with strictly postive and bounded section curvature with injiective radius approch to zero?

I think one may consturct these examples from beger’s spheres, but I cannot do it rigiously.

## Injectivity of the simple closed curves under geometric intersection number

Let $$\Sigma$$ be a closed surface of genus $$g\geq 2$$ and $$\mathcal{C}$$ be the set of all free homotopy classes of simple closed curves in $$\Sigma$$. Define $$i:\mathcal{C}\rightarrow \mathbb{R}^{\mathcal{C}}$$ by $$i(x)(y)=i(x,y)$$ for $$x,y\in \mathcal{C}$$ where $$i(x,y)$$ is the geometric intersection number.

Q) Does there exist a finite subset $$K\subset\mathcal{C}$$ such that $$i:\mathcal{C}\rightarrow R^{K}$$ is injective?

## Prove the injectivity and differentiability of x(u,v) = (u cos(v), u sin(v), $\frac{u^2}{2}$)

Prove the injectivity and differentiability of

x(u,v) = (u cos(v), u sin(v), $$\frac{u^2}{2}$$)

where:

u $$\epsilon$$ (0,inf), v $$\epsilon$$ (0,2$$\pi$$)

What I really want to prove is that (U,x) is a simple surface.

where U=(0,inf)x(0,2$$\pi$$)