Questions tagged [arithmetic-progression]
An arithmetic progression is a (possibly infinite) sequence of numbers such that the difference between consecutive terms is always the same value.
176 questions
0 votes
0 answers
196 views
Number of smooth numbers in arithmetic progression
I am currently reading about the distribution of smooth numbers in arithmetic progressions, such as https://tenenb.perso.math.cnrs.fr/PPP/PropStatFriables.pdf and https://math.dartmouth.edu/~carlp/PDF/...
- 281
4 votes
0 answers
246 views
Non-Wieferich primes in "general" arithmetic progressions
Let $a\geq 2$ be an integer. A prime $p$ is said to be Wieferich to base $a$ if $$ a^{p-1}\equiv 1\pmod{p^2}. $$ Silverman ("Wieferich’s criterion and the abc-conjecture") showed that the $...
- 151
1 vote
1 answer
184 views
Can a sparse set of residue classes cover all integers up to $E$?
Consider the following setup: Let $E$ be an large even integer For every odd prime $p < \sqrt{E}$, choose two residue classes modulo $p$: One class $a \bmod p$, where $a \equiv E \bmod p$ One ...
- 31
5 votes
2 answers
266 views
Solution-free set structure for x + 3y = z
I've been considering this theorem, theorem 1.2 in https://users.renyi.hu/~sos/1999_On_the_Structure_of_Sum_Free_Sets_2.pdf, that states $$ \textbf{Theorem } \quad \text{If } A \subseteq [n] \text{ is ...
12 votes
1 answer
545 views
Collection closed under symmetric difference and translation
Basically my question is the following. Suppose $\mathcal{H}$ is a collection of finite subsets of the natural numbers (containing at least one non-empty set) closed under symmetric difference and ...
- 731
6 votes
1 answer
296 views
Is it possible that the number of $\mathcal{T}$-algebras is an arithmetic progression?
For a single-sorted algebraic theory $\mathcal{T}$ denote by $t_n$ the number of $\mathcal{T}$-algebras with $n$ elements (up to isomorphism). Is there an example for $\mathcal{T}$ such that ...
- 65.1k
2 votes
1 answer
168 views
Explicit construction of integers with prescribed digit sum and residue class conditions
Let $q\geq 2$ be an integer, and $p,m\in \mathbb{N}$. Let $S_q$ be the function sum of digits in base $q$. If $\gcd(q-1,m)=1$, I was wondering if there is simple way to construct $k\in \mathbb{N}$ ...
- 23
4 votes
1 answer
138 views
APs in sumsets of exponential growing sequences
I posted this initially on SE, but after I didn't found a particular reference on it, I decided it would be more appropriate to post it here. A friend shared this observation with me and I thought ...
- 83
4 votes
2 answers
514 views
Number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$
I was wondering about sets that do not contain any $3$-term AP, and came to know that the official name of such a set is Salem–Spencer set. I was considering the question of counting the number of ...
- 1,256
8 votes
1 answer
439 views
Expected number of coin flips before you see a $k$-term arithmetic progression of heads
Flip a fair coin repeatedly and independently. Stop at the smallest $n$ such that you see a $k$-term arithmetic progression in $\{1, \dots, n\}$, all of whose positions are heads. What is the ...
- 9,900
-8 votes
2 answers
541 views
Infinite set intersection with arithmetic progressions
Let $\mathcal{A}$ be the set of all arithmetic progressions in $\mathbb{N}$ i.e \begin{align*} \mathcal{A} = \{a + b\mathbb{N} : a,b\in\mathbb{N}, b\neq 0\}. \end{align*} Does there exist a set $X \...
0 votes
1 answer
479 views
Goldbach conjecture reformulation [closed]
As thought, the question below is a reformulation of the goldbach conjecture. $ S = \{K - ap \mid a \geq 3, p \text{ is prime} < K/2 \} $, where $ a $ is an odd integer greater than or equal to 3, ...
- 31
9 votes
2 answers
769 views
Does every big polyomino contain a big arithmetic progression?
Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP. Is it true that for every $k$ ...
- 19.8k
5 votes
1 answer
197 views
Beating trivial bound for $k$-AP-free sets in characteristic $k$
Given integers $k,n\ge 1$, I shall write $\Bbb{Z}_k^n := (\Bbb{Z}/k\Bbb{Z})^n$. Fix $k\ge 3$. Let $r_k(\Bbb{Z}_k^n)$ denote the cardinality of the largest $A\subset \Bbb{Z}_k^n$, such that $A$ does ...
- 3,509
1 vote
0 answers
95 views
Progressions in finite fields with bounded hamming weight
Given $k\ge 2$ and an additive set $S$ (understood to live some implicit group $G$), define $$\Delta_k(S) := \left\{ d \in G: \bigcap_{i=1}^k (S+i\cdot d) \neq \emptyset \right\} $$(i.e., this is the ...
- 3,509