Skip to main content
MathOverflow

Return to Answer

added 45 characters in body
Source Link
Stefano Gogioso
Stefano Gogioso
  • 627
  • 5
  • 13

Let's consider a commutative $R$-algebra satisfying assumptions 1 and 2 in the question, where $R$ is a commutative ring. Let's start with a few observations:

  1. For every $U \subseteq \{1,...,n\}$, we have $a_U := \prod_{u \in U}a_u \neq 0$. Otherwise, $\prod_{u=1}^n a_u = 0$, which contradicts assumption 2 in the question. (We set $a_\emptyset = 1$ by convention).

  2. For every $U, V \subseteq \{1,...,n\}$, if $a_U = a_V$ then necessarily $U = V$. To see this, assume that $a_U = a_V$ and that $U \neq V$. Without loss of generality assume $U \not\subseteq V$ and let $x \in U \backslash V$. Then $0 = a_x^2a_{U \backslash\{x\}}= a_{V \sqcup \{x\}}\neq 0$. Conclude by contradiction with point 1 above.

For each $U \subseteq V$ write $q_U^V$ for the quotient map of $R$-modules $q_U^V: R a_U \rightarrow R a_V$ defined by $x \mapsto x a_{V \backslash U}$. Write $K := R a_{\{1,...,n\}})$ and $q_U := q_U^{\{1,...,n\}}: R a_U \rightarrow K$. We can now prove an interesting fact about $R$-linear combinations of the $a_U$ elements, namely that if for some coefficients $x_U \in R$ we have $\sum_{U \subseteq \{1,...,n\}} x_U a_U = 0$ then for every $V \subseteq \{1,...,n\}$ we also have: $$ \sum_{U \subseteq V} q_U^{U\sqcup \overline{V}}\!\!\left(x_U\right) a_{U \sqcup \overline{V}} = \left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right)a_{\overline{V}} = 0 $$ where we have written $\overline{V} := \{1,...,n\} \backslash V$. In particular, if $\mathcal{U}\subset \mathcal{P}$ is an antichain (i.e. if for all $U, V \in \mathcal{U}$ we have that $U \subseteq V$ implies $U=V$), then the elements $(a_U)_{U \in \mathcal{U}}$ are linearly independent over some suitable $R$(non-linearly independenttrivial) quotient of $R$. Because there are antichains $\mathcal{U}$ with size exponential in $n$, e.g. those formed by subsets $U$ with size $\frac{n}{2}$ for even $n$, this is an indication that computation in the $R$-algebra is not going to be efficient over some suitable (non-trivial) quotient of $R$.

PS: I think this last argument can be made formal by defining a surjective ring homomorphism $f: S \rightarrow Q$ from the sub-ring $S$ spanned by $R$-linear combinations of the elements $a_U$ for all $U \subseteq \{1,...,n\}$ to a suitable quotient ring $Q$ of $K[a_1,...,a_n]/(a_1^2,...,a_n^2)$ as follows: $$ f\left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right) := \sum_{U \subseteq \{1,...,n\}} q_U(x_U) a_U $$ I have not worked out the details yet, I might do so in the future if of interest.

Let's consider a commutative $R$-algebra satisfying assumptions 1 and 2 in the question, where $R$ is a commutative ring. Let's start with a few observations:

  1. For every $U \subseteq \{1,...,n\}$, we have $a_U := \prod_{u \in U}a_u \neq 0$. Otherwise, $\prod_{u=1}^n a_u = 0$, which contradicts assumption 2 in the question. (We set $a_\emptyset = 1$ by convention).

  2. For every $U, V \subseteq \{1,...,n\}$, if $a_U = a_V$ then necessarily $U = V$. To see this, assume that $a_U = a_V$ and that $U \neq V$. Without loss of generality assume $U \not\subseteq V$ and let $x \in U \backslash V$. Then $0 = a_x^2a_{U \backslash\{x\}}= a_{V \sqcup \{x\}}\neq 0$. Conclude by contradiction with point 1 above.

For each $U \subseteq V$ write $q_U^V$ for the quotient map of $R$-modules $q_U^V: R a_U \rightarrow R a_V$ defined by $x \mapsto x a_{V \backslash U}$. Write $K := R a_{\{1,...,n\}})$ and $q_U := q_U^{\{1,...,n\}}: R a_U \rightarrow K$. We can now prove an interesting fact about $R$-linear combinations of the $a_U$ elements, namely that if for some coefficients $x_U \in R$ we have $\sum_{U \subseteq \{1,...,n\}} x_U a_U = 0$ then for every $V \subseteq \{1,...,n\}$ we also have: $$ \sum_{U \subseteq V} q_U^{U\sqcup \overline{V}}\!\!\left(x_U\right) a_{U \sqcup \overline{V}} = \left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right)a_{\overline{V}} = 0 $$ where we have written $\overline{V} := \{1,...,n\} \backslash V$. In particular, if $\mathcal{U}\subset \mathcal{P}$ is an antichain (i.e. if for all $U, V \in \mathcal{U}$ we have that $U \subseteq V$ implies $U=V$), then the elements $(a_U)_{U \in \mathcal{U}}$ are $R$-linearly independent. Because there are antichains $\mathcal{U}$ with size exponential in $n$, e.g. those formed by subsets $U$ with size $\frac{n}{2}$ for even $n$, this is an indication that computation in the $R$-algebra is not going to be efficient over $R$.

PS: I think this last argument can be made formal by defining a surjective ring homomorphism $f: S \rightarrow Q$ from the sub-ring $S$ spanned by $R$-linear combinations of the elements $a_U$ for all $U \subseteq \{1,...,n\}$ to a suitable quotient ring $Q$ of $K[a_1,...,a_n]/(a_1^2,...,a_n^2)$ as follows: $$ f\left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right) := \sum_{U \subseteq \{1,...,n\}} q_U(x_U) a_U $$ I have not worked out the details yet, I might do so in the future if of interest.

Let's consider a commutative $R$-algebra satisfying assumptions 1 and 2 in the question, where $R$ is a commutative ring. Let's start with a few observations:

  1. For every $U \subseteq \{1,...,n\}$, we have $a_U := \prod_{u \in U}a_u \neq 0$. Otherwise, $\prod_{u=1}^n a_u = 0$, which contradicts assumption 2 in the question. (We set $a_\emptyset = 1$ by convention).

  2. For every $U, V \subseteq \{1,...,n\}$, if $a_U = a_V$ then necessarily $U = V$. To see this, assume that $a_U = a_V$ and that $U \neq V$. Without loss of generality assume $U \not\subseteq V$ and let $x \in U \backslash V$. Then $0 = a_x^2a_{U \backslash\{x\}}= a_{V \sqcup \{x\}}\neq 0$. Conclude by contradiction with point 1 above.

For each $U \subseteq V$ write $q_U^V$ for the quotient map of $R$-modules $q_U^V: R a_U \rightarrow R a_V$ defined by $x \mapsto x a_{V \backslash U}$. Write $K := R a_{\{1,...,n\}})$ and $q_U := q_U^{\{1,...,n\}}: R a_U \rightarrow K$. We can now prove an interesting fact about $R$-linear combinations of the $a_U$ elements, namely that if for some coefficients $x_U \in R$ we have $\sum_{U \subseteq \{1,...,n\}} x_U a_U = 0$ then for every $V \subseteq \{1,...,n\}$ we also have: $$ \sum_{U \subseteq V} q_U^{U\sqcup \overline{V}}\!\!\left(x_U\right) a_{U \sqcup \overline{V}} = \left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right)a_{\overline{V}} = 0 $$ where we have written $\overline{V} := \{1,...,n\} \backslash V$. In particular, if $\mathcal{U}\subset \mathcal{P}$ is an antichain (i.e. if for all $U, V \in \mathcal{U}$ we have that $U \subseteq V$ implies $U=V$), then the elements $(a_U)_{U \in \mathcal{U}}$ are linearly independent over some suitable (non-trivial) quotient of $R$. Because there are antichains $\mathcal{U}$ with size exponential in $n$, e.g. those formed by subsets $U$ with size $\frac{n}{2}$ for even $n$, this is an indication that computation in the $R$-algebra is not going to be efficient over some suitable (non-trivial) quotient of $R$.

PS: I think this last argument can be made formal by defining a surjective ring homomorphism $f: S \rightarrow Q$ from the sub-ring $S$ spanned by $R$-linear combinations of the elements $a_U$ for all $U \subseteq \{1,...,n\}$ to a suitable quotient ring $Q$ of $K[a_1,...,a_n]/(a_1^2,...,a_n^2)$ as follows: $$ f\left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right) := \sum_{U \subseteq \{1,...,n\}} q_U(x_U) a_U $$ I have not worked out the details yet, I might do so in the future if of interest.

Source Link
Stefano Gogioso
Stefano Gogioso
  • 627
  • 5
  • 13

Let's consider a commutative $R$-algebra satisfying assumptions 1 and 2 in the question, where $R$ is a commutative ring. Let's start with a few observations:

  1. For every $U \subseteq \{1,...,n\}$, we have $a_U := \prod_{u \in U}a_u \neq 0$. Otherwise, $\prod_{u=1}^n a_u = 0$, which contradicts assumption 2 in the question. (We set $a_\emptyset = 1$ by convention).

  2. For every $U, V \subseteq \{1,...,n\}$, if $a_U = a_V$ then necessarily $U = V$. To see this, assume that $a_U = a_V$ and that $U \neq V$. Without loss of generality assume $U \not\subseteq V$ and let $x \in U \backslash V$. Then $0 = a_x^2a_{U \backslash\{x\}}= a_{V \sqcup \{x\}}\neq 0$. Conclude by contradiction with point 1 above.

For each $U \subseteq V$ write $q_U^V$ for the quotient map of $R$-modules $q_U^V: R a_U \rightarrow R a_V$ defined by $x \mapsto x a_{V \backslash U}$. Write $K := R a_{\{1,...,n\}})$ and $q_U := q_U^{\{1,...,n\}}: R a_U \rightarrow K$. We can now prove an interesting fact about $R$-linear combinations of the $a_U$ elements, namely that if for some coefficients $x_U \in R$ we have $\sum_{U \subseteq \{1,...,n\}} x_U a_U = 0$ then for every $V \subseteq \{1,...,n\}$ we also have: $$ \sum_{U \subseteq V} q_U^{U\sqcup \overline{V}}\!\!\left(x_U\right) a_{U \sqcup \overline{V}} = \left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right)a_{\overline{V}} = 0 $$ where we have written $\overline{V} := \{1,...,n\} \backslash V$. In particular, if $\mathcal{U}\subset \mathcal{P}$ is an antichain (i.e. if for all $U, V \in \mathcal{U}$ we have that $U \subseteq V$ implies $U=V$), then the elements $(a_U)_{U \in \mathcal{U}}$ are $R$-linearly independent. Because there are antichains $\mathcal{U}$ with size exponential in $n$, e.g. those formed by subsets $U$ with size $\frac{n}{2}$ for even $n$, this is an indication that computation in the $R$-algebra is not going to be efficient over $R$.

PS: I think this last argument can be made formal by defining a surjective ring homomorphism $f: S \rightarrow Q$ from the sub-ring $S$ spanned by $R$-linear combinations of the elements $a_U$ for all $U \subseteq \{1,...,n\}$ to a suitable quotient ring $Q$ of $K[a_1,...,a_n]/(a_1^2,...,a_n^2)$ as follows: $$ f\left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right) := \sum_{U \subseteq \{1,...,n\}} q_U(x_U) a_U $$ I have not worked out the details yet, I might do so in the future if of interest.