Let's consider
$$\max_{x\in \mathbb{R}} x $$
subject to $x*3=1$. We know optimal value will be $\in \mathbb{R}^1$ and further based on properties of the polytope formed by the constraints, without being aware of the objective we can find that the polytope is $\{1/3\}$ so given the constraints we actually need 0 bits to represent the solution which is a far cry from $\infty$ bits. Let's consider $0<=x*3<=1$ similarily unaware of the objective. There are 3 possible solutions depending on the objectives. $x=0$, $x=1/3$ or $x\in [0,1/3]$ the third case reflects that the objective is orthogonal to the facet of the symplex holding the optimal solution or the objective weighted by $\vec 0$ face. Luckily you didn't ask for an encoding to all the solutions but of the encoding of one solution which we can do with just one bit.
This is not a pathology of one dimensional case. If there is a feasible and optimal point there has to be one on the vertices of the polytope. Also for any vertex of a polytope there exists an objective for which that corner is uniquely among the optimal point. So we need atleast $\log_2(\#\text{vertices count})$ bits. Formula for maximum vertex count. For fixed dimension this grows $\log_2(\text{polynomial}(k))$ where the order of the polynomial depends $n$. This encoding is not very useful though. One property would want from an encoding is to read of the solution from the encoding.
A finite information componentwise interpretable encoding
The next construction rests on two claims:
Given a bounded $G \subset \mathbb{Z}$ any polytope $Ax<=b$ with
$A\in G^{m\times n}$ and $b \in G^n$ which is bounded all its
vertices are rational. There is a finite number of distinct rational numbers which appear in those vertices. There exist a largest $s$ rational number whose integers multiples can represent any of rational numbers appearing in the vertices.
Given a bounded $G \subset \mathbb{Z}$ any polytope $Ax<=b$ with
$A\in G^{m\times n}$ and $b \in G^n$ projected
on any axis results is an interval. These intervals have a bounded length $d \in \mathbb{Q}^+$ depending on $(m,n,G)$.
${d\over s} \in \mathbb{Z}$ by construction. Any vertex of $Ax<=b$ is $ \in ([-|{d\over s}|, |{d\over s}|] \cap \mathbb{Z} )^n * s $ which we can represent with $n \lceil \log_2 ({2*d\over s}) \rceil$ bits.
How large are $d$ and $s$?
$(\prod_{g \in G} |g|)^{(m+1) n}$ is a valid $1 \over s$. There are way tighter bounds though.
For bounding $d$ i don't have a formula, however we can calculate $d \over 2$ using a MINLP program.
It involves insections of the most slightly non parallel hyper planes being as far away from each other as possible using integers available as coefficients from $G$.
The maximum objective of this program in the JuMP modeling language calculates $d\over 2 $ in for $n=2$, $m=2$ by finding a pairs of equality constraints in $\mathbb{R}^2$ such that the point defined by the pairs intersection has a maximal squared first component.
using JuMP, Gurobi
l =-2
u = 1
M = max(l^2, u^2)
m = Model(Gurobi.Optimizer)
set_attribute(m, "Presolve", 2)
set_attribute(m, "NonConvex", 2)
set_attribute(m, "FeasibilityTol", 1.1e-9)
@variable(m, -1.0e11 <= x[1:2] <= 1.0e11)
#mess with this bound and Gurobi cries. It obviously limits the validity of the program, but those errors are dominated by Gurobis minimal "FeasibilityTol" of 1.0e-9. Don't trust it to be correct for large numbers.
@variable(m, l<= b[1:2] <= u,Int)
@variable(m, l<= a[1:2,1:2] <= u,Int)
@constraint(m, a[:,:]*x[:] == b[:]) # Two linear inequalities
@objective(m, Max, (x[1])^2)
@variable(m, 0 <= s[1:2] <= M *2, Int)
for j in 1:2 @constraint(m, s[j] == sum( a[j,:].* a[j,:])) end
@variable(m, M *-2 <= c <= M *2, Int)
@constraint(m, c == sum( a[1,:].* a[2,:])) # scalar product between the equations
@constraint(m, c*c + 1 <= s[1]*s[2])
# We want them not being colinear, so we impose <a[1,:], a[2,:]>^2 < ||a[1,:]||^2*||a[2,:]||^2, since all coefficients are integer +1 is actually a safe epsilon to impose this.
optimize!(m)
For $G = \mathbb{Z} \cap [-1,0] $ $d=2$ holds. For $G = \mathbb{Z} \cap [-1,1] $ $d=8$ holds. For $G = \mathbb{Z} \cap [-2,1] $ $d=8$ holds. For $G = \mathbb{Z} \cap [-8,7] $ $d=28800$ holds. Beyond this (and maybe also earlier) you will need a rational solver to get accurate results. I am not aware of such a solver. I hope you can discover a structure which let's you build an upper bound for $d$ with this. Representing the $\{0, 1, 2, 5\}$ requires additional binary variables.
An idea for a $d(m,m,G)$
This might be the most amplying square matrix. It assumes without loss of much generality that $|\min G| \leq \max G$.
