All Questions
16 questions
54
votes
2
answers
8k
views
Walsh Fourier transform of the Möbius function
This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly orthogonal to Morse
August Ferdinand Möbius (November 17, 1790 – ...
- 1,446
22
votes
2
answers
6k
views
$\mathbf{P} = \mathbf{NP}$, what's the problem?
Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$.
We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...
- 2,912
13
votes
1
answer
2k
views
Erdős multiplication problem revisited
This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.
The very problem has been discussed in-depth and, as such, I require no ...
- 32.1k
4
votes
1
answer
209
views
Finding a binary variable assignment to make a matrix with variables singular (over F_p)
Consider a square matrix defined over a finite field $M\in\mathbb{F}_p^{n\times n}$ having the following form
$$M=\begin{bmatrix}a_{11}+b_{11}x_1&a_{12}+b_{12}x_1&\dots&a_{1n}+b_{1n}x_1\\...
- 14k
1
vote
0
answers
209
views
Solution to system of linear equations
Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
- 13.9k
2
votes
0
answers
81
views
Number of solutions to linear diophantine equations, with natural coefficients in a box
Let c, k, d $ \in \mathbb{N} $, let a, x $ \in \mathbb{N}^k $ suppose for all i $ \leq $ k, $ x_i \leq d $, $ a_i \in \mathcal{O}(d2^i) $ and $ \sum{a_ix_i} = c $ my question is for the value of c ...
9
votes
0
answers
2k
views
Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere
Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
- 82.7k
19
votes
1
answer
616
views
How hard is it to tell when a finite set tiles the integers?
Given a nonempty set $B$ of integers between 1 and $n$, we wish to determine whether or not $\mathbb{Z}$ can be tiled with translates of $B$ (that is, covered by disjoint translates of $B$). I know an ...
- 30.1k
2
votes
1
answer
240
views
valuation from $\mathbb{Z}^n$ into $\mathbb{Z}$. Easy way?
Let $\mathcal{F}:=\{f_a\}_{a\in\mathbb{Z}}$ be a set of symbols indexed by the integers and satisfying the rules:
$$f_a=f_{-a} \qquad \text{and} \qquad f_af_b=f_{a+b}+f_{a-b}.$$
Define a linear ...
- 43.2k
1
vote
1
answer
603
views
The smallest altitude amongst the triangles formed by points in the unit circle
Let $S$ be a finite set of points inside the unit circle. Consider all possible triangles formed by three distinct points in $S$, and among all such triangles find the smallest altitude. Denote this ...
CommunityBot
- 1
19
votes
1
answer
3k
views
Möbius Randomness of the Rudin-Shapiro Sequence
The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is defined as follows.
Let $a_n = \sum \epsilon_i\epsilon_{i+1}$ where $\epsilon_1,\epsilon_2,\dots$ are the digits in the ...
CommunityBot
- 1
3
votes
3
answers
2k
views
Problem regarding subsets that sum to 0
Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset ...
- 9,114
8
votes
3
answers
947
views
Boolean Cube of Primes
For a large enough $n$, and a parameter $ m $ I'm looking for a subset of the prime numbers in the range $[n,2n]$ with a unique structure. I am looking for a prime $p$ and a set of $m$ positive (not ...
- 1
3
votes
3
answers
852
views
A conjecture on a Subset Power Sum Problem motivated by Computer Science
Let $X=\{x_{1}, \cdots , x_{n}\}$ be a set of $n$ positive integers and integer $i \ge 1$. Let’s say that the set $X$ is $i$-sum-avoiding if for any nonnegative integers $c_{1}, \cdots, c_{n}$ such ...
- 1
10
votes
3
answers
649
views
Efficiently getting bits of N! ?
Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?
i.e....
CommunityBot
- 1
13
votes
0
answers
713
views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
CommunityBot
- 1