Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Basically, I wonder whether a theory similar to geometric group theory has been or could be developed for rings and semirings.

One direction would be the following. Consider $\mathbb{N}$ (with the French convention, i.e. including $0$), and let $n\in\mathbb{N}$. Consider all algorithms based on the following operations:

  • adding $1$,
  • multiplying two variables,
  • summing two variables

and allowed to have any number of local variables (no loops or other advanced programming, just allocation of variables -for free- and the above three operations). Let $\delta(n)$ be the least number of operations needed for such an algorithm to return $n$.

What can we say about the function $\delta$? Can it be generalized to other rings or semi-rings? Can it be turned into a distance? Does it say something about the algebra of the given ring or semi-ring?

(the emphasis was added in edit, this is the part I am most interested in).

It feels a little bit like Kolmogorov complexity (except that I chose not to allow taking differences of variables, which is questionable).

Edit Another direction would be to consider the minimal numbers $||n||$ of $1$s needed to write $n$ by a well-formed formula with the symbols $1$ $+$ $\times$ $($ and $)$; this happens to lead to open questions, see this answer on MOthis answer on MO.

There could be many other ways to turn finitely generated rings or semi-rings into geometric object, I would be interested in any of them.

Added in edit To clarify where I'm headed to, both cases show that there are natural ways to construct functions that can play the role of the distance to $0$; but I am not aware of any distance functions (taking two arguments) of this sort. Is there any that has been considered?

Basically, I wonder whether a theory similar to geometric group theory has been or could be developed for rings and semirings.

One direction would be the following. Consider $\mathbb{N}$ (with the French convention, i.e. including $0$), and let $n\in\mathbb{N}$. Consider all algorithms based on the following operations:

  • adding $1$,
  • multiplying two variables,
  • summing two variables

and allowed to have any number of local variables (no loops or other advanced programming, just allocation of variables -for free- and the above three operations). Let $\delta(n)$ be the least number of operations needed for such an algorithm to return $n$.

What can we say about the function $\delta$? Can it be generalized to other rings or semi-rings? Can it be turned into a distance? Does it say something about the algebra of the given ring or semi-ring?

(the emphasis was added in edit, this is the part I am most interested in).

It feels a little bit like Kolmogorov complexity (except that I chose not to allow taking differences of variables, which is questionable).

Edit Another direction would be to consider the minimal numbers $||n||$ of $1$s needed to write $n$ by a well-formed formula with the symbols $1$ $+$ $\times$ $($ and $)$; this happens to lead to open questions, see this answer on MO.

There could be many other ways to turn finitely generated rings or semi-rings into geometric object, I would be interested in any of them.

Added in edit To clarify where I'm headed to, both cases show that there are natural ways to construct functions that can play the role of the distance to $0$; but I am not aware of any distance functions (taking two arguments) of this sort. Is there any that has been considered?

Basically, I wonder whether a theory similar to geometric group theory has been or could be developed for rings and semirings.

One direction would be the following. Consider $\mathbb{N}$ (with the French convention, i.e. including $0$), and let $n\in\mathbb{N}$. Consider all algorithms based on the following operations:

  • adding $1$,
  • multiplying two variables,
  • summing two variables

and allowed to have any number of local variables (no loops or other advanced programming, just allocation of variables -for free- and the above three operations). Let $\delta(n)$ be the least number of operations needed for such an algorithm to return $n$.

What can we say about the function $\delta$? Can it be generalized to other rings or semi-rings? Can it be turned into a distance? Does it say something about the algebra of the given ring or semi-ring?

(the emphasis was added in edit, this is the part I am most interested in).

It feels a little bit like Kolmogorov complexity (except that I chose not to allow taking differences of variables, which is questionable).

Edit Another direction would be to consider the minimal numbers $||n||$ of $1$s needed to write $n$ by a well-formed formula with the symbols $1$ $+$ $\times$ $($ and $)$; this happens to lead to open questions, see this answer on MO.

There could be many other ways to turn finitely generated rings or semi-rings into geometric object, I would be interested in any of them.

Added in edit To clarify where I'm headed to, both cases show that there are natural ways to construct functions that can play the role of the distance to $0$; but I am not aware of any distance functions (taking two arguments) of this sort. Is there any that has been considered?

added 666 characters in body
Source Link
Benoît Kloeckner
  • 14.4k
  • 1
  • 60
  • 106

Basically, I wonder whether a theory similar to geometric group theory has been or could be developed for rings and semirings.

One direction would be the following. Consider $\mathbb{N}$ (with the French convention, i.e. including $0$), and let $n\in\mathbb{N}$. Consider all algorithms based on the following operations:

  • adding $1$,
  • multiplying two variables,
  • summing two variables

and allowed to have any number of local variables (no loops or other advanced programming, just allocation of variables -for free- and the above three operations). Let $\delta(n)$ be the least number of operations needed for such an algorithm to return $n$.

What can we say about the function $\delta$? Can it be generalized to other rings or semi-rings? Can it be turned into a distance?Can it be turned into a distance? Does it say something about the algebra of the given ring or semi-ring?

(the emphasis was added in edit, this is the part I am most interested in).

It feels a little bit like Kolmogorov complexity (except that I chose not to allow taking differences of variables, which is questionable).

Edit Another direction would be to consider the minimal numbers $||n||$ of $1$s needed to write $n$ by a well-formed formula with the symbols $1$ $+$ $\times$ $($ and $)$; this happens to lead to open questions, see this answer on MO.

There could be many other ways to turn finitely generated rings or semi-rings into geometric object, I would be interested in any of them.

Added in edit To clarify where I'm headed to, both cases show that there are natural ways to construct functions that can play the role of the distance to $0$; but I am not aware of any distance functions (taking two arguments) of this sort. Is there any that has been considered?

Basically, I wonder whether a theory similar to geometric group theory has been or could be developed for rings and semirings.

One direction would be the following. Consider $\mathbb{N}$ (with the French convention, i.e. including $0$), and let $n\in\mathbb{N}$. Consider all algorithms based on the following operations:

  • adding $1$,
  • multiplying two variables,
  • summing two variables

and allowed to have any number of local variables (no loops or other advanced programming, just allocation of variables -for free- and the above three operations). Let $\delta(n)$ be the least number of operations needed for such an algorithm to return $n$.

What can we say about the function $\delta$? Can it be generalized to other rings or semi-rings? Can it be turned into a distance? Does it say something about the algebra of the given ring or semi-ring?

It feels a little bit like Kolmogorov complexity (except that I chose not to allow taking differences of variables, which is questionable).

There could be many other ways to turn finitely generated rings or semi-rings into geometric object, I would be interested in any of them.

Basically, I wonder whether a theory similar to geometric group theory has been or could be developed for rings and semirings.

One direction would be the following. Consider $\mathbb{N}$ (with the French convention, i.e. including $0$), and let $n\in\mathbb{N}$. Consider all algorithms based on the following operations:

  • adding $1$,
  • multiplying two variables,
  • summing two variables

and allowed to have any number of local variables (no loops or other advanced programming, just allocation of variables -for free- and the above three operations). Let $\delta(n)$ be the least number of operations needed for such an algorithm to return $n$.

What can we say about the function $\delta$? Can it be generalized to other rings or semi-rings? Can it be turned into a distance? Does it say something about the algebra of the given ring or semi-ring?

(the emphasis was added in edit, this is the part I am most interested in).

It feels a little bit like Kolmogorov complexity (except that I chose not to allow taking differences of variables, which is questionable).

Edit Another direction would be to consider the minimal numbers $||n||$ of $1$s needed to write $n$ by a well-formed formula with the symbols $1$ $+$ $\times$ $($ and $)$; this happens to lead to open questions, see this answer on MO.

There could be many other ways to turn finitely generated rings or semi-rings into geometric object, I would be interested in any of them.

Added in edit To clarify where I'm headed to, both cases show that there are natural ways to construct functions that can play the role of the distance to $0$; but I am not aware of any distance functions (taking two arguments) of this sort. Is there any that has been considered?

Source Link
Benoît Kloeckner
  • 14.4k
  • 1
  • 60
  • 106

Geometry of rings and semi-rings

Basically, I wonder whether a theory similar to geometric group theory has been or could be developed for rings and semirings.

One direction would be the following. Consider $\mathbb{N}$ (with the French convention, i.e. including $0$), and let $n\in\mathbb{N}$. Consider all algorithms based on the following operations:

  • adding $1$,
  • multiplying two variables,
  • summing two variables

and allowed to have any number of local variables (no loops or other advanced programming, just allocation of variables -for free- and the above three operations). Let $\delta(n)$ be the least number of operations needed for such an algorithm to return $n$.

What can we say about the function $\delta$? Can it be generalized to other rings or semi-rings? Can it be turned into a distance? Does it say something about the algebra of the given ring or semi-ring?

It feels a little bit like Kolmogorov complexity (except that I chose not to allow taking differences of variables, which is questionable).

There could be many other ways to turn finitely generated rings or semi-rings into geometric object, I would be interested in any of them.