This paper investigates the expressive power and mechanisms of Transformer for sequence modeling with long, sparse, and complex memories. The study systematically examines how different components of Transformer, such as dot-product self-attention, positional encoding, and feed-forward layers, affect its expressive power. Through explicit approximation rates, the research reveals the roles of key parameters like the number of layers and attention heads. Theoretical insights are validated experimentally and provide guidance for alternative architectures. The paper categorizes three types of sequence modeling tasks: (1) modeling fixed, long but sparse memories, (2) modeling adaptive, long but sparse memories, and (3) modeling essentially sparse memories. For each task, the study theoretically investigates the expressive power of Transformer and its variants, establishing explicit approximation rates. The analysis provides insights into the underlying mechanisms of Transformer components, including the distinct roles of the number of layers, attention heads, and feed-forward layer width. It also explores the functionality and necessity of dot-product attention and the efficiency of relative positional encoding (RPE) in modeling long-range correlations. Theoretical results show that for fixed, long but sparse memories, a single-layer Transformer with sufficient attention heads and feed-forward width can suffice. For adaptive memories, the cooperation between dot-product and RPE is crucial for modeling adaptive memories. The study also demonstrates that RPE can efficiently model long-range correlations, particularly for essentially sparse memories, overcoming the "curse of memory" faced by recurrent neural networks. The paper also discusses the necessity of dot-product attention and the efficiency of alternative structures. It shows that for certain tasks, dot-product attention is not necessary, and computationally efficient alternatives can be used. Theoretical results are supported by experiments, validating the insights into the expressive power and mechanisms of Transformer. The study contributes to a deeper understanding of Transformer's capabilities in sequence modeling with long, sparse, and complex memories.This paper investigates the expressive power and mechanisms of Transformer for sequence modeling with long, sparse, and complex memories. The study systematically examines how different components of Transformer, such as dot-product self-attention, positional encoding, and feed-forward layers, affect its expressive power. Through explicit approximation rates, the research reveals the roles of key parameters like the number of layers and attention heads. Theoretical insights are validated experimentally and provide guidance for alternative architectures. The paper categorizes three types of sequence modeling tasks: (1) modeling fixed, long but sparse memories, (2) modeling adaptive, long but sparse memories, and (3) modeling essentially sparse memories. For each task, the study theoretically investigates the expressive power of Transformer and its variants, establishing explicit approximation rates. The analysis provides insights into the underlying mechanisms of Transformer components, including the distinct roles of the number of layers, attention heads, and feed-forward layer width. It also explores the functionality and necessity of dot-product attention and the efficiency of relative positional encoding (RPE) in modeling long-range correlations. Theoretical results show that for fixed, long but sparse memories, a single-layer Transformer with sufficient attention heads and feed-forward width can suffice. For adaptive memories, the cooperation between dot-product and RPE is crucial for modeling adaptive memories. The study also demonstrates that RPE can efficiently model long-range correlations, particularly for essentially sparse memories, overcoming the "curse of memory" faced by recurrent neural networks. The paper also discusses the necessity of dot-product attention and the efficiency of alternative structures. It shows that for certain tasks, dot-product attention is not necessary, and computationally efficient alternatives can be used. Theoretical results are supported by experiments, validating the insights into the expressive power and mechanisms of Transformer. The study contributes to a deeper understanding of Transformer's capabilities in sequence modeling with long, sparse, and complex memories.