Four-variable FE mod n

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Four-variable FE mod n

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: PRELMO 2023/3 (http://tinyurl.com/PRELMO)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#1 h Jul 11, 2023, 6:27 PM • 1 Y

Y by MS_asdfgzxcvb

Let $n$ be a positive integer, and let $\mathbb Z/n\mathbb Z$ denote the integers modulo $n$ . Determine the number of functions $f:(\mathbb Z/n\mathbb Z)^4\to\mathbb Z/n\mathbb Z$ satisfying $\begin{align*} &f(a,b,c,d)+f(a+b,c,d,e)+f(a,b,c+d,e)\\ &=f(b,c,d,e)+f(a,b+c,d,e)+f(a,b,c,d+e). \end{align*}$ for all $a,b,c,d,e\in\mathbb Z/n\mathbb Z$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11291 posts

#2 h Apr 15, 2025, 2:34 AM

Y by

bump, unsolved $~~~~~~~~~$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1488 posts

#3 h Apr 19, 2025, 7:03 PM • 1 Y

Y by yofro

Scam problem; it turns out this is a standard exercise in group cohomology. Rename $n$ to $m$ . The answer is $m^{m^3-m^2+m}$ . Write $G = \mathbb Z / m \mathbb Z$ .

For any ring $R$ (commutative with unity) two $R$ -modules $A$ and $B$ , given any projective resolution of $A$ ,
$\cdots \stackrel{d_3}{\longrightarrow} P_2 \stackrel{d_2}\longrightarrow P_1 \stackrel{d_1}\longrightarrow P_0 \stackrel{\varepsilon}\longrightarrow A \longrightarrow 0,$ we can consider the corresponding cochain complex given by applying the contravariant functor $\operatorname{Hom}_R (-, B)$ and ignoring $A$ :
$0 \stackrel{d^0}\longrightarrow \operatorname{Hom}_R (P_0, B) \stackrel{d^1}\longrightarrow \operatorname{Hom}_R (P_1, B) \stackrel{d^2}\longrightarrow \operatorname{Hom}_R (P_2, B) \stackrel{d^3}\longrightarrow \cdots.$ It is a basic fact of homological algebra that the cohomology $\ker d^{n+1} / \operatorname{im} d^n$ of this cochain complex does not depend on the choice of projective resolution; we denote this $R$ -module as $\operatorname {Ext} _{R}^{n}(A,B)$ .

To see why this is useful, it turns out that considering $\mathbb Z$ as a $\mathbb Z[G]$ -module where $G$ acts trivially, there is a famous free resolution called the bar resolution
$\cdots \stackrel{d_3}{\longrightarrow} F_2 \stackrel{d_2}\longrightarrow F_1 \stackrel{d_1}\longrightarrow F_0 \stackrel{\varepsilon}\longrightarrow \mathbb Z \longrightarrow 0,$ where $F_n$ is the $\mathbb Z[G]$ module with group structure $\mathbb Z[G]^{\otimes (n+1)}$ and module structure on simple tensors given by $g \cdot (g_0 \otimes g_1 \otimes \dots \otimes g_n) = (gg_0) \otimes g_1 \otimes \dots \otimes g_n$ , $\varepsilon$ is the augmentation map (taking each $g \in G$ to $1$ ), and each $d_n$ is given by extending the map
$\begin{align*} d_n(g_0 \otimes g_1 \otimes \dots \otimes g_n) &= \sum_{i=0}^{n-1} (-1)^i g_0 \otimes \dots \otimes g_i g_{i+1} \otimes \dots \otimes g_n \\ &\quad\;\;+ (-1)^n g_0 \otimes \dots \otimes g_{n-1}. \end{align*}$ Now consider the $\mathbb Z[G]$ -module $B := \mathbb Z / m\mathbb Z$ where $G$ acts trivially (the fact that this is the same group as $G$ is a coincidence), and apply the contravariant functor $\operatorname{Hom}_{\mathbb Z[G]} (-, B)$ to get a cochain complex,
$0 \stackrel{d^0}\longrightarrow \operatorname{Hom}_{\mathbb Z[G]} (F_0, B) \stackrel{d^1}\longrightarrow\operatorname{Hom}_{\mathbb Z[G]} (F_1, B) \stackrel{d^2}\longrightarrow \operatorname{Hom}_{\mathbb Z[G]} (F_2, B) \stackrel{d^3}\longrightarrow \cdots.$ Considering each $F_n$ as a free $\mathbb Z[G]$ -module with basis $1 \otimes g_1 \otimes \dots \otimes g_n$ for $g_1, \dots, g_n \in G$ , the group structure of $\operatorname{Hom}_{\mathbb Z[G]} (F_n, B)$ is isomorphic to abelian group of functions $G^n \to B$ under pointwise addition, and the map $d^n$ is given by the map
$\begin{align*} d^n(f) (g_1, \dots, g_n) &= g_1 \cdot f(g_2, \dots, g_n) + \sum_{i=1}^{n-1} (-1)^i f(g_1, \dots, g_i g_{i+1}, \dots, g_n) \\ &\quad\;\;+ (-1)^n f(g_1, \dots, g_{n-1}). \end{align*}$ And voilà, since $g_1$ acts trivially, we wish to find the size of $\ker d^5$ . Now using the definition of $\operatorname{Ext}$ and the first isomorphism theorem, we get
$\begin{align*} \# \ker d^5 &= \# \operatorname{Ext}_{\mathbb Z[G]}^4 (\mathbb Z, B) \cdot \#\operatorname{im} d^4 \\ &= \# \operatorname{Ext}_{\mathbb Z[G]}^4 (\mathbb Z, B) \cdot \frac{\# \operatorname{dom} d^4}{\#\ker d^4} \\ &\hdots \\ &= \prod_{n=0}^4 \left(\# \operatorname{Ext}_{\mathbb Z[G]}^n (\mathbb Z, B) \cdot \#\operatorname{dom} d^n\right)^{(-1)^{4-n}}. \end{align*}$ Of course, for $n \ge 1$ , we have $\operatorname{dom} d^n = \operatorname{Hom}_{\mathbb Z[G]} (F_{n-1}, B)$ which has $m^{m^{n-1}}$ elements, and $\operatorname{dom} d^0 = 0$ , so it suffices to compute $\# \operatorname{Ext}_{\mathbb Z[G]}^n (\mathbb Z, B)$ . To do this, we'll consider a different projective resolution of the $\mathbb Z[G]$ -module $\mathbb Z$ . Specifically, if $\sigma$ is a generator of $G$ , then we can check that $N := 1+\sigma+\sigma^2+\dots+\sigma^{m-1}$ satisfies $N(1-\sigma) = 0$ , so we have the free resolution
$\cdots \stackrel{\times (1 - \sigma)}{\longrightarrow} \mathbb Z[G] \stackrel{\times N}\longrightarrow \mathbb Z[G] \stackrel{\times (1 - \sigma)}\longrightarrow \mathbb Z[G] \stackrel{\varepsilon}\longrightarrow \mathbb Z \longrightarrow 0,$ where again $\varepsilon$ takes any $g \in G$ to $1$ (See the example on Dummit and Foote p. 801). This has corresponding chain complex under $\operatorname{Hom}_{\mathbb Z[G]} (-, B)$ ,
$0 \longrightarrow B \stackrel{0}{\longrightarrow} B \stackrel{0}\longrightarrow B \stackrel{0}\longrightarrow \cdots,$ (every morphism is $0$ ) under the identification $\operatorname{Hom}_{\mathbb Z[G]} (\mathbb Z[G], B) \cong B$ since $\sigma$ acts as $1$ . Thus, $\# \operatorname{Ext}_{\mathbb Z[G]}^n (\mathbb Z, B) = |B|$ for all $n$ , and we have
$\# \ker d^5 = m^{m^3 - m^2 + m^1 - m^0 + 0} \cdot m^{1 - 1 + 1 - 1 + 1} = m^{m^3 - m^2 + m},$ where the first term is the contribution from $\operatorname{dom}$ and the second term is the contribution from $\operatorname{Ext}$ , as desired.

This post has been edited 2 times. Last edited by cosmicgenius, Apr 19, 2025, 7:05 PM
Reason: typos v2

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a