Direct product representation of a function?

[Stephen Tashi]

When do functions have representations as a "direct product"?

For example, If I have a function f(x) given by the ordered pairs:
\{(1,6),(2,4),(3,5),(4,2),(5,3),(6,1) \}

We could (arbitrarily) declare that integers in certain sets have certain "properties":
\{ 1,3\} have property A
\{5,6\} have property B
\{4,2\} have property C
\{1,5,4\} have property X
\{3,6,2\} have property Y

With that stipulation, each of the six integers can be given a unique "coordinate" representation as set of properties:
1 = [A,X]
3 = [A,Y]
5 = [B,X]
6 = [B,Y]
4 = [C,X]
2 = [C,Y]

The function f(x) is the "direct product" of the functions given by
g(x) = \{(A,B), (B,A), (C,C) \}
h(x) = \{(X,Y),(Y,X)\}
in the sense that if you apply those functions to the respective "coordinates" of an integer, you determine the integer that f(x) maps it to. For example (A,X) \rightarrow (B,Y) implies f(x) maps 1 \rightarrow 6.

Perhaps this is a generalization of "separation of variables".

 

[fzero]

Your coordinate representation is not a direct product, it is the intersection of sets.

 

[Stephen Tashi]

Your coordinate representation is not a direct product, it is the intersection of sets.

Both the coordinate representation and the fact that f(x) can be represented as operations on coordinates are significant. After all, the direct product of algebraic objects involves more than the fact that an element of the direct product is equal to the intersection of sets defined by coordinate values.

As far as I know, this example is not literally a "direct product" in the sense of a direct product of algebraic objects, which is why I put "direct product" in quotes. Perhaps a category theorist can find a way to look at it as a coproduct in some category.

 

[fzero]

You have an isomorphism $f$ of a set of integers $X$ to itself. This is a function but the restriction to an isomorphism is so strong that we cannot claim to derive results about general functions by considering it.

We have some rules for defining subsets $X_i$ of $X$ such that the union of all of the subsets is $X$ and a sufficient number of intersections defines a partition $\{U_i\}$ of $X$. It is natural to consider the restriction of $f$ to the subsets $f_i = f|_{X_i}$. You are going further and restriction to the partitions $f|_{U_i}$. But the partitions only contain a single integer and since $f$ is an isomorphism, the image of $_{U_i}$ is a single point. So all we've done is relabeled $f$.

I think you've chosen an over-restrictive example, so all you are doing is relabeling the elements of the initial set by some new partition. Since the the function is an isomorphism, the function itself just corresponds to a relabeling of the elements of the set. We are not really saying anything interesting about the function because the example has been chosen with nearly the least amount of structure possible.

It is interesting to define classes, either by defining subsets of the initial set or on classes of functions. One could consider equivalence classes under some symmetry operation for example. Then one can consider restrictions to equivalences classes, or similar things. But I think you want to loosen up the guiding example in order to have some structure that would allow nontrivial results.

 

[Stephen Tashi]

You have an isomorphism $f$ of a set of integers $X$ to itself.

Yes, the function f(x) is technically a function mapping an integer to an integer, but we can "in an obvious manner" use it define another function that maps sets of integers to sets on integers. Abusing notation by also calling this second function f, we have that f is an isomorphism with respect to the set operations (such as \cup, \cap ).

This is a function but the restriction to an isomorphism is so strong that we cannot claim to derive results about general functions by considering it.

It would surprise me if an arbitrary 1-to-1 function allows separation of variables, so my ambition is not derive results about general functions. In fact, I'm not at the level of deriving results at all. I'm just developing my intuitive appreciation of the situation.

For that purpose, your formulation below is very helpful:

We have some rules for defining subsets $X_i$ of $X$ such that the union of all of the subsets is $X$ and a sufficient number of intersections defines a partition $\{U_i\}$ of $X$. It is natural to consider the restriction of $f$ to the subsets $f_i = f|_{X_i}$.

You are going further and restriction to the partitions $f|_{U_i}$. But the partitions only contain a single integer and since $f$ is an isomorphism, the image of $_{U_i}$ is a single point. So all we've done is relabeled $f$.

I think you've chosen an over-restrictive example, so all you are doing is relabeling the elements of the initial set by some new partition.

As I said, I agree that the example is special. What I don't intuitively grasp yet is whether is whether the same "trick" could be applied to an arbitrary 1-to-1 function when we have complete freedom in defining the list of "properties". For example, suppose we change f(x) by given it the ordered pairs ((4,4),(2,2) instead of (4,2), (2,4).

It is interesting to define classes, either by defining subsets of the initial set or on classes of functions. One could consider equivalence classes under some symmetry operation for example.

If we go so far as to consider whether the elements in the common domain of a set of 1-to-1 functions can be given a set of properties such that each function is represented by functions that operate on the "coordinates" of an element then I think this amounts to asking whether a semigroup can be decomposed as a direct product. I don't want to expand the scope of the question till it reaches that familiar territory. But it would interest me to understand intuitively how the ability to represent individual functions as functions on coordinates relates to that question. i.e. Are there sets of functions such that for each function , we can invent properties that "coordinatize" an element of the domain and represent the function as functions of coordinates, but that we can never find one particular set of properties that let's us do this for all the functions in the set of functions? To my current intuition, a semigroup could fail to decompose as direct product is that manner (where each individual function can be written as a function on "coordinates" but no common coordinate system exists) or it could fail because it contains one function that cannot be written as a function of coordinates. However, I don't know if that intutition is correct. Are both situations actually possible?

 

[Stephen Tashi]

It isn't clear to me how standard the terminology "direct product" of functions is, but I'll take the definition to be the natural one ( http://mathoverflow.net/questions/1...irect-products-of-other-functions-question-ab )

For the case of a 1-to-1 mapping f of a finite set onto itself, the question of whether it can be represented in some non-trivial way as a direct product g\ \times \ h becomes a problem in number theory. (Permutations and number theory are not my favorite subjects, but they hold sway here.)

The mapping f is a permutation. A permutation has a representation as a product of disjoint cycles.

Suppose, for example, that g is a permutation consisting of a single 2-cycle and h is a permutation consisting of a single 3-cycle. Then g \times h is a function that is a single 6-cycle since 6 is the least common multiple of 2 and 3. In general, if f is a permutation consisting of single k-cycle, in order to express f as a direct product of two functions you need to express k as the least common multiple of two other integers.

When f consists of a product of several disjoint cycles, I think you need an algorithm that looks for possible g and h by trying to find two sets of cycles such that each k_i -cycle in f can be put into 1-to-1 correspondence with a pair of cycles consisting of a k_r-cycle of g and a k_s-cycle of h such that k_i = L.C.M\ (k_r,\ k_s).