<p>Given $n, k \in \mathbb{N}$, we create a set $S \subseteq \mathbb{Z}_m^k$ by treating it as an $n\times k$ grid and choosing each $S_{ij}$ by sampling from $\mathbb{Z}_m$, such that $P(S_{ij} = z) = p_z$. We'll define the occupant count $o$ to be the total number of non-zero elements from every vector, and we'll call the quantity $o/nk = 1 - \alpha$. We can think of $\alpha$ as the probability, if we were to probe our grid at random, that we would find a zero. I want to constrain my sets to some known $\alpha$ and then have $p_{z\neq 0} = p_{0\neq x\neq z}$. Clearly if $\forall x, y \in \mathbb{Z}_m, p_z = p_x$, this condition is met, but more generally, we can reason that </p>

<p>$\sum_{z \neq 0}p_z + \alpha$ = 1$</p>

<p>$\sum_{z \neq 0}p_z = (n - 1)p_z$</p>

<p>$(n - 1)p_z + \alpha = 1$</p>

<p>$p_z = \frac{1 - \alpha}{n-1}$</p>

<p>Then I can construct a graph $G$ where $V = S$ and the edge relation is defined as:</p>

<p>$E = \{ (x, y) \mid \langle x,y\rangle = 0 \}$</p>

<blockquote>
  <p>What I want to know is if we choose uniformly $x, y \in S$, what is
  $P((x, y) \in E)$?</p>
</blockquote>

<p>A question I'd be quite willing to hear answered as well is the case when $S = \mathbb{Z}_n^k$.</p>

<p>I suspect that this probability will rise with $n$'s compositeness where $k &gt; n$. It'd be curious if you could compute the number.</p>

CC BY-SA 3.0
2017-03-23T18:23:23.067Z
What is m in the above question, and how does it relate to n?
daniello
CC BY-SA 3.0
2017-03-23T19:57:12.323Z
That was a screwup on my part, there is only $n$. I'll fix it when I get back to a computer or someone else could.
Samuel Schlesinger
<finite-fields>
Module Independence Graphs
Samuel Schlesinger
# Module Independence Graphs

(Asked by: username_0 on 2017-03-22)

Given $n, k \in \mathbb{N}$, we create a set $S \subseteq \mathbb{Z}\_m^k$ by treating it as an $n\times k$ grid and choosing each $S\_{ij}$ by sampling from $\mathbb{Z}\_m$, such that $P(S\_{ij} = z) = p\_z$. We'll define the occupant count $o$ to be the total number of non-zero elements from every vector, and we'll call the quantity $o/nk = 1 - \alpha$. We can think of $\alpha$ as the probability, if we were to probe our grid at random, that we would find a zero. I want to constrain my sets to some known $\alpha$ and then have $p\_{z\neq 0} = p\_{0\neq x\neq z}$. Clearly if $\forall x, y \in \mathbb{Z}\_m, p\_z = p\_x$, this condition is met, but more generally, we can reason that

$\sum\_{z \neq 0}p\_z + \alpha$ = 1$

$\sum\_{z \neq 0}p\_z = (n - 1)p\_z$

$(n - 1)p\_z + \alpha = 1$

$p\_z = \frac{1 - \alpha}{n-1}$

Then I can construct a graph $G$ where $V = S$ and the edge relation is defined as:

$E = \{ (x, y) \mid \langle x,y\rangle = 0 \}$

> What I want to know is if we choose uniformly $x, y \in S$, what is
> $P((x, y) \in E)$?

A question I'd be quite willing to hear answered as well is the case when $S = \mathbb{Z}\_n^k$.

I suspect that this probability will rise with $n$'s compositeness where $k > n$. It'd be curious if you could compute the number.

**Tags:** finite-fields

> **Comments:**
> **username_1**: What is m in the above question, and how does it relate to n?  
> **username_0**: That was a screwup on my part, there is only $n$. I'll fix it when I get back to a computer or someone else could.  

---

## 0 answers

