Is this function of partitions one-to-one?

Question

Suppose we have a set of integers $H=\{1,2, ...n\}$. Let $A$ a set of partitions of H into $n/2$ pairs $\{\{x_1,y_1\},\{x_2,y_2\}, ...,\{x_{n/2},y_{n/2}\}\}$ and function $f:A \rightarrow Z^n$ where $f(\{\{x_1,y_1\},\{x_2,y_2\}, ...,\{x_{n/2},y_{n/2}\}\})=\cup \{x_i*y_i\}$.

For a set of integers $\{1,2, ...8\}$ and the pairing $\{\{3,6\},\{1,7\},\{2,4\},\{5,8\}\}$

$f(\{\{3,6\},\{1,7\},\{2,4\},\{5,8\}\})=\{18,7,8,40\}$

Is this function injective?

Your notation is very strange (what is $n$?). I think you are asking about the function $f: \Bbb{P}(\Bbb{Z} \times \Bbb{Z}) \to \Bbb{P}(\Bbb{Z})$ such that $f(A) = { xy \mid (x, y) \in A}$. This is not injective, e.g., $f({(3, 6)}) = f({2, 9}) = {18}$. — Rob Arthan, Oct 19 '21 at 20:58
No. The members of the domain of rhe function $f$ as indicated by your example are sets of pairs: so the domain comprises all sets of pairs $\Bbb{P}(\Bbb{Z} \times \Bbb{Z})$. What you wrote, namely, $(\Bbb{Z} \times \Bbb{Z})^n$ means the set of $n$-tuples of pairs, not sets. — Rob Arthan, Oct 19 '21 at 21:02
@RobArthan Yes, I mean set of n-tuple pairs of {1,2,3, ..., 2n} — Mohammad Al-Turkistany, Oct 19 '21 at 21:04
Sorry, it is a set of n/2 pairs. Please suggest proper notation — Mohammad Al-Turkistany, Oct 19 '21 at 21:08
See my earlier comments for the power-set notation. If you are specifically interested in sets of a certain size, you can say ${A : \Bbb{P}(X) \mid |A| = n/2}$ where $X = {1, 2, \ldots, 8}$ or whatever. The mapping cannot be injective even if your restrict the cardinality, since $xy = yx$, while $(x, y) \neq (y, x)$. You should edit your question to make it clear exactly what you are asking. — Rob Arthan, Oct 19 '21 at 21:12
Order does matter in the standard notion of pairing $(x, y)$. In any case you have identities like $1 \cdot 4 = 2 \cdot 2$, which prevent the mapping being injective, even if you treat the pairs as unorderd. — Rob Arthan, Oct 19 '21 at 21:16
If you want unordered pairs, then you write them like this ${a, b}$. — Rob Arthan, Oct 19 '21 at 21:18
@RobArthan here is the motivation: https://www.quantamagazine.org/the-sum-product-problem-shows-how-addition-and-multiplication-constrain-each-other-20190206/ — Mohammad Al-Turkistany, Oct 19 '21 at 21:18
@RobArthan I will fix the notation according to your suggestions — Mohammad Al-Turkistany, Oct 19 '21 at 21:20
@RobArthan Fixed it. (2,2) is not allowed in partitions of {1,2,3, ... n} — Mohammad Al-Turkistany, Oct 19 '21 at 21:31

paw88789 · Accepted Answer · 2021-10-19T23:10:43.547

4

Here are two partitions of $\{1,2,3,4,5,6,7,8\}$ that give the same products:

$\{\{1,6\}, \{2,4\}, \{3,8\}, \{5,7\}\}$ and $\{\{2,3\},\{1,8\},\{4,6\},\{5,7\}\}$

It is perhaps worth observing that any prime in the upper half of the interval must pair with the same thing in both partitions.

edited Oct 19 '21 at 23:10

answered Oct 19 '21 at 22:59

paw88789

40,402

score 2 · Answer 2 · answered Oct 19 '21 at 22:49

No. For $n$ large enough, $f$ will not be injective.

It's easier to consider the case of addition, where we have $$1 + (-1) = 0, \qquad 2 + (-3) = -1, \qquad 3 + (-2) = 1 \\ 1 + (-2) = -1, \qquad 2 + (-1) = 1, \qquad 3 + (-3) = 0$$ That is, partition $\{-3,-2,-1, 1, 2, 3\}$ into three parts of size $2$ in at least two ways that give the same set of sums.

This answers your question by applying the map $x \mapsto 2^{x+3}$ to find $$2^{1+3}2^{(-1)+3} = 2^{0+6}, \qquad 2^{2+3}2^{(-3)+3} = 2^{-1+6}, \qquad 2^{3+3}2^{(-2)+3} = 2^{1+6} \\ 2^{1+3}2^{(-2)+3} = 2^{-1+6}, \qquad 2^{2+3}2^{(-1)+3} = 2^{1+6}, \qquad 2^{3+3}2^{(-3)+3} = 2^{0+6}$$ so we find that $f$ is not injective for $n \geq 2^6 =64$. [it likely fails to be injective for smaller values as well]

Is this function of partitions one-to-one?

2 Answers2