1
$\begingroup$

Let $u,v\in\{0,1\}^n$ be $0-1$ vectors with $n$ components.

Let $I=\langle u,v \rangle$. Clearly $I$ can take values in $\{0,1,\dots,n-1,n\}$.

How many different values can $$I'=\frac{\langle u,v \rangle}{\sqrt{\langle u,u \rangle\langle v,v \rangle}}$$ take?

The question is essentially, how many different angles can one make?

A calculation is shown here https://math.stackexchange.com/questions/1058925/number-of-different-normalized-inner-products stating the number is around $cn^{2.75}$. Is there a proof for this?

$\endgroup$
3
  • $\begingroup$ An interesting question on its own is the cardinality of $A_n=\{a\cdot b|a,b\in \{1,\dots,n\} \}$. If one can show that $|A_n|=O(n^{1.75})$ the above follows from the arguments in the link. $\endgroup$
    – user35593
    Dec 10, 2014 at 9:21
  • $\begingroup$ $$|A_n|=n^2-\sum_{n<p<n^2, prime} \lfloor \frac{n^2}{p}\rfloor.$$ So there seems to be a connection with the distribution of primes. $\endgroup$
    – user35593
    Dec 10, 2014 at 9:34
  • $\begingroup$ Could you explain more as an answer? $\endgroup$
    – Turbo
    Dec 10, 2014 at 15:32

1 Answer 1

1
$\begingroup$

Here is the explanation of my comment however its not a solution to the problem. For $m\in \mathbb{N}$ let $[m]=\{1,\dots,m\}$. We have $$A_n=[n^2]-\{m\in [n^2]|\nexists a,b \in [n] \text{ with } m=ab\}\\ \subset [n^2]-\{m\in [n^2]|\exists\; prime\; p>n, \; p|m\}\\ =[n^2]-\{kp\in [n^2]|p>n\; prime, kp<n^2\}\\ $$ When I wrote the comment I made an error and thought there is equal sign everywhere. For a prime $p$ with $n<p<n^2$ we have $kp<n^2$ for all $k\in \{1,\dots,\lceil \frac{n^2}{p}\rceil\}$. Hence $$|A_n|\leq n^2-\sum_{n<p<n^2, prime} \lceil \frac{n^2}{p}\rceil.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.