5
votes
1answer
455 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
7
votes
1answer
340 views

Building a polyhedron from areas of its faces

Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for ...
0
votes
1answer
253 views

[Matrices over Z] - An algorithm for calculating the diagonal with elementary operations

Dear mathoverflow, Let $ \left( \begin{array}{cc} a & b \newline c & d \end{array} \right) $ be a matrix with $a, b, c, d \in \mathbb{Z}$, $\gcd(a,b,c,d) = 1$ and $ad - bc = \pm N$, with $N ...
13
votes
0answers
1k views

Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes). Is there an efficient way to calculate this?